首页 > 代码库 > 《数据结构与算法分析：C语言描述》复习——第九章“图论”——多源最短路径问题
《数据结构与算法分析：C语言描述》复习——第九章“图论”——多源最短路径问题
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 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。