Dijkstra单源最短路径

发表于   |   分类于   |  

关于最短路径

给定一张图，从一点出发，到达图中所有点的最短路径。

该性质描述为：如果P(i,j)={Vi....Vk..Vs...Vj}是从顶点i到j的最短路径，k和s是这条路径上的一个中间顶点，那么P(k,s)必定是从k到s的最短路径。下面证明该性质的正确性。

假设P(i,j)={Vi....Vk..Vs...Vj}是从顶点i到j的最短路径，则有P(i,j)=P(i,k)+P(k,s)+P(s,j)。而P(k,s)不是从k到s的最短距离，那么必定存在另一条从k到s的最短路径P'(k,s)，那么P'(i,j)=P(i,k)+P'(k,s)+P(s,j)<P(i,j)。则与P(i,j)是从i到j的最短路径相矛盾。因此该性质得证。

由上述性质可知，如果存在一条从i到j的最短路径(Vi.....Vk,Vj)，Vk是Vj前面的一顶点。那么(Vi...Vk)也必定是从i到k的最短路径。为了求出最短路径，Dijkstra就提出了以最短路径长度递增，逐次生成最短路径的算法。譬如对于源顶点V0，首先选择其直接相邻的顶点中长度最短的顶点Vi，那么当前已知可得从V0到达Vj顶点的最短距离dist[j]=min{dist[j],dist[i]+matrix[i][j]}。根据这种思路，

假设存在G=<V,E>，源顶点为V0，U={V0},dist[i]记录V0到i的最短距离，path[i]记录从V0到i路径上的i前面的一个顶点。

  1. 从V-U中选择使dist[i]值最小的顶点i，将i加入到U中；
  2. 更新与i直接相邻顶点的dist值。(dist[j]=min{dist[j],dist[i]+matrix[i][j]})
  3. 直到U=V，停止。

[CODE]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
#include <iostream>
#include <cstring>
#include <string>
#include <stack>
using namespace std;
struct Graphs{
   	int n;
   	int e;
   	int matrix[50][50];
   	string spots[50];
};
void shortestPath(Graphs g, int *dist, int *path, int v0){
   	// 初始化
   	int *visited = new int[g.n];
   	memset(visited, 0, sizeof(int) * g.n);
   	for (int i = 0; i < g.n; i++){
       	if (g.matrix[v0][i] >= 0 && i != v0){
           	dist[i] = g.matrix[v0][i];
           	path[i] = v0;
       	}
       	else{
           	dist[i] = INT_MAX;
           	path[i] = -1;
       	}
   	}
   	dist[v0] = 0;
   	path[v0] = v0;
   	visited[v0] = 1;
   	
   	// 重复n-1次
   	for (int i = 1; i < g.n; i++){
       	int min = INT_MAX;
       	int prev;
       	//找出最近的未visit的节点
       	for (int j = 0; j < g.n; j++){
           	if (visited[j] == 0 && dist[j] < min){
               	min = dist[j];
               	prev = j;
           	}
       	}
       	visited[prev] = 1;
       	// 更新所有节点的距离
       	for (int j = 0; j < g.n; j++){
           	if (visited[j] == 0 && dist[j] > dist[prev] + g.matrix[prev][j] && g.matrix[prev][j] >= 0){
               	dist[j] = g.matrix[prev][j] + dist[prev];
               	path[j] = prev;
           	}
       	}
   	}
}

void showPath(Graphs g, int *path, int v0, int ve){
   	stack<int> path_stack;
   	int cur = ve;
   	int last;
   	while (cur != v0){
       	path_stack.push(cur);
       	cur = path[cur];
   	}
   	cout << g.spots[v0];
   	last = v0;
   	while (!path_stack.empty()){
       	cur = path_stack.top();
       	path_stack.pop();
       	cout << "->(" << g.matrix[last][cur] << ")->" << g.spots[cur];
       	last = cur;
   	}
   	cout << endl;
}

int main(){
   	int N, E, R;
   	Graphs park;
   	cin >> N;
   	park.n = N;
   	for (int i = 0; i < N; i++){
       	for (int j = 0; j < N; j++){
           	park.matrix[i][j] = -1;
       	}
       	park.matrix[i][i] = 0;
   	}
   	for (int i = 0; i < N; i++){
       	cin >> park.spots[i];
   	}
   	cin >> E;
   	string src, dst;
   	int src_n = 0, dst_n = 0,length;
   	park.e = E;
   	for (int i = 0; i < E; i++){
       	cin >> src >> dst >> length;
       	for (int j = 0; j < park.n; j++){
           	if (src == park.spots[j]) src_n = j;
           	if (dst == park.spots[j]) dst_n = j;
       	}
       	park.matrix[src_n][dst_n] = length;
       	park.matrix[dst_n][src_n] = length;
   	}
   	cin >> R;
   	for (int i = 0; i < R; i++){
       	cin >> src >> dst;
       	for (int j = 0; j < park.n; j++){
           	if (src == park.spots[j]) src_n = j;
           	if (dst == park.spots[j]) dst_n = j;
       	}
       	int path[50], dist[50];
       	shortestPath(park, dist, path, src_n);
       	showPath(park, path, src_n, dst_n);
   	}
   	return 0;
}