91精品国产乱码久久久久久,久久香蕉一级毛片,久久精品国产亚洲AV麻豆网站

每對頂點間的最短路徑之Floyd-Warshall算法

        Floyd-Warshall算法的基本思路是：
   1.用D[v][w]記錄每對頂點間的最短距離
   2.對每一個圖中的頂點，以其作為基點掃描每一對D[v][w]，檢驗是否通過該基點可以使得這對頂點間的距離變小。

我們實際是很容易就可以寫出這個算法的代碼：

#define N 100

void Floyd(int dist[N][N],int n)

{

int i,j,k;

for(k=0;k<n;k++)

for(i=0;i<n;i++)

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

if(dist[i][k]+dist[k][j]<dist[i][j])

dist[i][j]=dist[i][k]+dist[k][j];

}

我們還面臨一個保存路徑的問題,如何來做呢？

#define N 100

int map[N][N];

void Floyd(int dist[N][N],int path[N][N],int n)

{

int i,j,k;

for(i=0;i<n;i++)

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

dist[i][j]=map[i][j],path[i][j]=0;

for(k=0;k<n;k++)

for(i=0;i<n;i++)

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

if(dist[i][k]+dist[k][j]<dist[i][j]){

dist[i][j]=dist[i][k]+dist[k][j];

path[i][j]=k;

}

void output(int i,int j)

{

if(i==j) return;

if(path[i][j]==0) cout<<j<<" ";

else{

output(i,path[i][j]);

output(path[i][j],j);

}

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

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

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

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

yuanyuelang

導航

留言簿

隨筆分類

文章分類

文章檔案

閱讀排行榜

評論排行榜

常用鏈接

統(tǒng)計

最新評論

每對頂點間的最短路徑之Floyd-Warshall算法