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 }