首页 > 代码库 > 《数据结构与算法分析：C语言描述》复习——第九章“图论”——单源带权最短路径问题
《数据结构与算法分析：C语言描述》复习——第九章“图论”——单源带权最短路径问题
2014.07.04 18:32
简介：
给定一个有向图，边的权值可能各不相同（不包含负权值）。给定一个起点s，找出起点到所有顶点的最短路径距离。
描述：
这就是Dijkstra算法的用武之处了。
实际上，如果从无权值的情况出发，来思考带权最短路径问题的解法，那么应该只需要修改几行之前BFS的代码就能解决问题。
对于无权值的情况，每条边的长度都是1，那么先搜到的路径必然也是最短的。当边的长度各不相同时，后搜到的路径也可能更短，因此加上对应的判断和更新代码即可。
实现：
1 // A simple illustration for weighted shortest path. Graph represented by adjacency matrix. 2 #include <iostream> 3 #include <queue> 4 #include <vector> 5 using namespace std; 6 7 const int INFINITY = 1000000000; 8 9 void weightedShortestPath(const vector<vector<int> > &graph, 10 vector<int> &dist, vector<bool> &reachable)11 {12 // The minimal distances from 0th vertice to others.13 int n;14 int i, j;15 16 n = (int)graph.size();17 dist.resize(n);18 reachable.resize(n);19 20 if (n < 1) {21 return;22 }23 24 for (i = 0; i < n; ++i) {25 reachable[i] = false;26 }27 28 queue<int> q;29 30 dist[0] = 0;31 reachable[0] = true;32 33 q.push(0);34 while (!q.empty()) {35 i = q.front();36 q.pop();37 for (j = 0; j < n; ++j) {38 if (graph[i][j] == INFINITY || (reachable[j] && 39 dist[i] + graph[i][j] >= dist[j])) {40 continue;41 }42 dist[j] = dist[i] + graph[i][j];43 if (!reachable[j]) {44 q.push(j);45 }46 reachable[j] = true;47 }48 }49 }50 51 int main()52 {53 vector<vector<int> > graph;54 vector<int> dist;55 vector<bool> reachable;56 int n;57 int nk;58 int i, j;59 int tmp, tmp_dist;60 61 while (cin >> n && n > 0) {62 graph.resize(n);63 for (i = 0; i < n; ++i) {64 graph[i].resize(n, INFINITY);65 }66 67 for (i = 0; i < n; ++i) {68 cin >> nk;69 for (j = 0; j < nk; ++j) {70 cin >> tmp >> tmp_dist;71 graph[i][tmp] = tmp_dist;72 }73 }74 75 weightedShortestPath(graph, dist, reachable);76 77 for (i = 0; i < n; ++i) {78 cout << i << ": ";79 if (reachable[i]) {80 cout << dist[i] << endl;81 } else {82 cout << "Unreachable" << endl;83 }84 }85 86 for (i = 0; i < n; ++i) {87 graph[i].clear();88 }89 graph.clear();90 }91 92 return 0;93 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。