yuanyuelang

留言簿

隨筆分類

文章分類

文章檔案

閱讀排行榜

評論排行榜

常用鏈接

統計

隨筆 - 0
文章 - 10
評論 - 5
引用 - 0

單源最短路徑之Dijkstra算法

單源最短路徑，解決的是什么問題呢？
顧名思義，單源說明從一個源出發，出發到哪里呢？不管到哪里我都要求得一個最短的路徑。

比較正式的說法：
對于有向圖G={V,E},帶權，注意Dijkstra算法要求所有的權值非負，
假設我們的源是s，源點要到達的點集合是S，我們每次選擇具有最短路徑估計的頂點u(u在V-S中，并將u加入到S中，然后此時要對u所有的出邊進行處理，怎么處理，我們要最短路徑，所以此時要判斷s經過u到達V-S中的點會不會比不經過u到達來的小，更新呵呵..

那么怎么寫成代碼呢？
1.我們需要二維數組graph[][]表示圖，用distance[]數組來表示源點V0到其它頂點的最短路徑distance[v]，我們還要保存具體路徑，我們用path[][]二維bool數組來表示,path[1]就表示源點到頂點V1的路徑，path[1][0,n-1]數組里面的元素如果為true表示V0有經過那些頂點到達V1
2.我們還要考慮到頂點是否已經加到S中，用一個flag數組來標志頂點是否已經求的最短路徑了。

還要分清是有向圖還是無向圖，這對于入邊和出邊在程序處理的時候要注意。

#define MAXN 100

#define INF 0xfffffff

//注意graph里面的數據，兩頂點i指向j有邊，長為r，則graph[i][j]=r,其余情況graph為INF，包括i==j

void dijkstra(int graph[MAXN][MAXN],bool path[MAXN][MAXN],int distance[],int n)

{

int i,j,min,vertex;

bool flag[MAXN];

for(i=0;i<n;i++){//初始化

distance[i]=graph[0][i];

flag[i]=false;

for(j=0;j<n;j++) path[i][j]=false;

if(distance[i]<INF){ //路徑必定至少有v0和vi兩個頂點

p[i][0]=true;p[i][i]=true;

}

flag[0]=true;

distance[0]=0;//注意一定要初始化distance[0]

for(i=1;i<n;i++){

min=INF;

for(j=1;j<n;j++)

if(!flag[j]&&distance[j]<min){//找到最近的點

min=distance[j];

vertex=j;

}

flag[vertex]=true;

for(j=1;j<n;j++)

if(!flag[j]&&graph[vertex][j]+min<distance[j]){//如果可以通過vertex更近的話,更新

distance[j]=graph[vertex][j]+min;

for(int k=0;k<n;k++) path[j][k]=path[vertex][k];

path[j][j]=true;

}

請讀者務必自己舉個例子，運行看看，這樣子才能理解好理解的根深蒂固，還有一定要自己不斷的寫，自己平常要鍛煉，做ACM題目時最好自己再寫一遍，不要太依賴模板了哈哈。。

posted on 2009-09-14 21:21 原語餓狼閱讀(635) 評論(0) 編輯收藏引用所屬分類: 圖論

只有注冊用戶登錄后才能發表評論。


相關文章: 每對頂點間的最短路徑之Floyd-Warshall算法單源最短路徑之Dijkstra算法最小生成樹之Prim算法最小生成樹之Kruskal算法

網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品