欧美大香线蕉线伊人久久,99热成人精品免费久久,久久综合狠狠色综合伊人

Floyd_Warshall算法

Posted on 2009-04-11 03:14 lzmagic 閱讀(2035) 評論(0) 編輯收藏引用所屬分類: Algorithm

/**

* FLOYD_WARSHALL 所有頂點對的最短路徑算法 (All-Pairs Shortest Path Algorithm)

* 輸入：圖g

* 輸出：所有頂點對的最短路徑長

* 結構：圖g用鄰接矩陣表示

* 算法：Floyd_Warshall算法(動態規劃)

* 復雜度：O(|V|^3)

#include <iostream>

#include <string>

#include <vector>

#include <deque>

#include <list>

#include <stack>

#include <queue>

#include <iterator>

#include <algorithm>

#include <numeric>

#include <functional>

#include <climits>

using namespace std;

int n;

vector<vector<int> > g;

vector<vector<int> > dist;

void Floyd_Warshall()

{

// 初始化dist，頂點間(無中間頂點)最短路徑長為邊長，頂點到自身的最短路徑長為0。

dist = g;

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

dist[i][i] = 0;

// 從頂點i到定點j且中間頂點皆屬于集合{0, 1, 2,

, k}的最短路徑長。

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

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

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

if (dist[i][k] < INT_MAX && dist[k][j] < INT_MAX)

dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);

}

int main()

{

n = 5;

g.assign(n, vector<int>(n, INT_MAX));

g[0][1] = 3; g[0][2] = 8; g[0][4] = -4;

g[1][3] = 1; g[1][4] = 7;

g[2][1] = 4;

g[3][0] = 2; g[3][2] = -5;

g[4][3] = 6;

Floyd_Warshall();

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

{

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

cout << dist[i][j] << ' ';

cout << endl;

}

system("pause");

return 0;

}

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

相關文章: Floyd_Warshall算法 Kruskal算法 Prim算法 Critical Path 關鍵路徑 Bellman_Ford算法 SPFA算法 Dijkstra算法 USP 無權最短路徑算法 Topsort 拓撲排序 (正則表達式)是否匹配(字符串) Quicksort 快速排序

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

lzm

導航

常用鏈接

留言簿(2)

隨筆分類(13)

隨筆檔案(14)

收藏夾(4)

最新隨筆

搜索

積分與排名

最新評論

閱讀排行榜

評論排行榜

Floyd_Warshall算法