《數據結構與算法分析》——“圖論”——多源最短路徑問題技术頭條網

《數據結構與算法分析》——“圖論”——多源最短路徑問題

2019-11-13 09:02:13 C語言編程

簡介：

給定一個帶權圖（有向無向皆可），找出每個頂點到其他所有頂點的最短距離。

描述：

此處介紹O(n^3)級別的Floyd算法，只需要用三層循環的簡單代碼就完成所有最短距離的計算。唯一需要注意的，就是三層循環裡i、j、k的擺放順序。

代碼非常簡單，所以無需多作解釋了。

實現：

 1 // A simple illustration for all pairs shortest path using Floyd Algorithm. 2 #include  3 #include  4 using namespace std; 5  6 const int INFINITY = 1000000000; 7  8 void floydAlgorithm(const vector > &graph,  9 vector > &dist)10 {11 int n;12 int i, j, k;13 14 n = (int)graph.size();15 dist.resize(n);16 for (i = 0; i < n; ++i) {17 dist[i].resize(n, INFINITY);18 }19 20 for (i = 0; i < n; ++i) {21 for (j = 0; j < n; ++j) {22 dist[i][j] = graph[i][j];23 }24 }25 26 for (k = 0; k < n; ++k) {27 for (i = 0; i < n; ++i) {28 for (j = 0; j < n; ++j) {29 if (dist[i][k] + dist[k][j] >= dist[i][j]) {30 continue;31 }32 dist[i][j] = dist[i][k] + dist[k][j];33 }34 }35 }36 }37 38 int main()39 {40 vector > graph;41 vector > dist;42 int n;43 int nk;44 int i, j;45 int tmp, tmp_dist;46 47 while (cin >> n && n > 0) {48 graph.resize(n);49 for (i = 0; i < n; ++i) {50 graph[i].resize(n, INFINITY);51 }52 53 for (i = 0; i < n; ++i) {54 cin >> nk;55 for (j = 0; j < nk; ++j) {56 cin >> tmp >> tmp_dist;57 graph[i][tmp] = tmp_dist;58 }59 }60 61 floydAlgorithm(graph, dist);62 63 for (i = 0; i < n; ++i) {64 for (j = 0; j < n; ++j) {65 cout << "[" << i << "][" << j << "]: ";66 if (dist[i][j] < INFINITY) {67 cout << dist[i][j] << endl;68 } else {69 cout << "Unreachable" << endl;70 }71 }72 }73 74 for (i = 0; i < n; ++i) {75 graph[i].clear();76 }77 graph.clear();78 79 for (i = 0; i < n; ++i) {
80 dist[i].clear();
81 }
82 dist.clear();
83 }
84 
85 return 0;
86 }

說在前面：小夥伴們在學習的過程中難免會遇到很多的困難，有的是初學不知道如何入手，亦或是想要繼續提升自己，小編為了幫助大家解決學習問題，大家可以點擊上方我的頭像私信我發送：“學習”兩個字，我將會針對性的幫助解答你學習上的問題和發送你學習資料哦，大家一起進步