《数据结构与算法分析：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 }