2014.07.04 19:34
简介：
给定一个带权图（有向无向皆可），找出每个顶点到其他所有顶点的最短距离。
描述：
此处介绍O(n^3)级别的Floyd算法，只需要用三层循环的简单代码就完成所有最短距离的计算。唯一需要注意的，就是三层循环里i、j、k的摆放顺序。
代码非常简单，所以无需多作解释了。
实现：
1 // A simple illustration for all pairs shortest path using Floyd Algorithm. 2 #include <iostream> 3 #include <vector> 4 using namespace std; 5 6 const int INFINITY = 1000000000; 7 8 void floydAlgorithm(const vector<vector<int> > &graph, 9 vector<vector<int> > &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<vector<int> > graph; 41 vector<vector<int> > 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 }