久久91精品久久91综合,久久ww精品w免费人成,久久精品国产免费一区

單源最短路徑之Dijkstra算法

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

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

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

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

#define MAXN 100

#define INF 0xfffffff

//注意graph里面的數(shù)據(jù)，兩頂點(diǎn)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兩個頂點(diǎn)

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){//找到最近的點(diǎn)

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;

}

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

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

只有注冊用戶登錄后才能發(fā)表評論。
【推薦】100%開源！大型工業(yè)跨平臺軟件C++源碼提供，建模，組態(tài)！

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

網(wǎng)站導(dǎo)航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

yuanyuelang

導(dǎo)航

留言簿

隨筆分類

文章分類

文章檔案

閱讀排行榜

評論排行榜

常用鏈接

統(tǒng)計(jì)

最新評論

單源最短路徑之Dijkstra算法