最短路径的Dijkstra算法
The Dijkstra Algorithm
摘要：本文用C实现了图的最短路径Dijkstra算法，并将自己理解该算法的方式与大家分享下，若有错误之处，欢迎指正。
关键字：图、最短路径、Graph、Dijkstra
一、引言 Introduction
对图G中的每一条边e都赋以一个实数w(e)，则G连同它边上的权称为赋权图。赋权图经常出现在图论的实际应用问题中，边上的权（Weight）可以表示各种实际意义，如在输送网络中，权可以表示两地的距离，可以表示运输的时间，还可以表示运输的费用等。许多最优化问题相当于在一个赋权图中找出某类具有最小（或最大）权的子图。例如，给出一个连接各城镇的铁路网，要找出一条给定两个城镇间的最短路线。这个问题的图论模型建立如下：以顶点代表城镇，边代表城镇间的铁路线，权表示直接相连的城镇之间的铁路距离，得到一个赋权图，即网络N。
本文讨论带权的有向图，并称路径上的第一个顶点为源点（Source），最后一个顶点为终点（Destination）。
二、算法理解 Understanding the Algorithm
Dijkstra算法描述为：假设用带权邻接矩阵来表示带权有向图。首先引进一个辅助向量D，它的每个分量D[i]表示当前所找到的从始点v到每个终点Vi的最短路径。它的初始状态为：若两顶点之间有弧，则D[i]为弧上的权值；否则置D[i]为无穷大。
u 找到与源点v最近的顶点，并将该顶点并入最终集合S；
u 根据找到的最近的顶点更新从源点v出发到集合V-S上可达顶点的最短路径；
u 重复以上操作。
图1 带权有向图
以前总是认为Dijkstra算法可以用来求从源点到指定终点的最短路径，导致总不能抓住算法的中心思想。现在认为把握Dijkstra的算法要点为：
u Dijkstra提出了一个按路径长度递增的次序产生最短路径的算法；
u 每次循环都可以得到一个从源点到某个顶点的最短路径，某个即不是确定的一个；
以带权有向图1为例说明Dijkstra算法的执行过程：假设源点为v0，则初始状态时源点到其它各顶点的距离为：
| 源点 终点 |
v1 |
v2 |
v3 |
v4 |
v5 |
| v0 |
∽ |
10 |
∽ |
30 |
100 |
由上表可知，与源点v0最近的顶点为v2，距离为10。
将v2加入到最终顶点集合S中。
再根据v2更新从源点到其它顶点的最短距离，即从v0-v2-v3的距离为60<∽，所以将v0到v3的距离更新为60，如下表所示：
| 源点 终点 |
v1 |
v2 |
v3 |
v4 |
v5 |
| v0 |
∽ |
10 |
60 |
30 |
100 |
由上表可知，与源点v0次近的顶点为v4，距离为30。
将v4加入到最终顶点集合S中；
再根据v4更新从源点到其它顶点的最短距离。即从v0-v4-v3的距离为50<60，所以将v0到v3的距离更新为50；从v0-v4-v5的距离为90<100，所以将v0到v5的距离更新为90。
| 源点 终点 |
v1 |
v2 |
v3 |
v4 |
v5 |
| v0 |
∽ |
10 |
50 |
30 |
90 |
重复以上操作……
直到最终集合包含了所有的顶点。
三、程序实现 Code
1
/*
2 * Copyright (c) 2013 eryar All Rights Reserved.
3 *
4 * File : Main.cpp
5 * Author : eryar@163.com
6 * Date : 2013-1-1 16:50
7 * Version : 0.1v
8 *
9 * Description : Use adjacency matrix of a graph.
10 * Use Dijkstra method to find the shortest path.
11 *
12 */
13
14 #include <CFLOAT>
15 #include <IOSTREAM>
16 using namespace std;
17
18 const int VERTEX_NUM = 20;
19 const double INFINITY = DBL_MAX;
20
21 // Arc of the graph.
22 typedef struct SArc
23 {
24 double dWeight;
25 }AdjMatrix[VERTEX_NUM][VERTEX_NUM];
26
27 // The graph: include vertex size and
28 // arc size also the adjacency matrix.
29 typedef struct SGraph
30 {
31 int mVertexSize;
32 int mArcSize;
33 int mVertex[VERTEX_NUM];
34 AdjMatrix mAdjMatrix;
35 }Graph;
36
37 // Function declarations.
38 void CreateGraph(Graph& graph, bool isDigraph = false);
39 int LocateVertex( const Graph& graph, int vertex);
40 void ShowGraph( const Graph& graph);
41 void Dijkstra( const Graph& graph, int src);
42
43 // Main function.
44 int main( int argc, char* argv[])
45 {
46 Graph graph;
47 int iSrc = 0;
48
49 CreateGraph(graph, true);
50
51 ShowGraph(graph);
52
53 cout<<"Input the source node of the shortest path:";
54 cin>>iSrc;
55
56 Dijkstra(graph, iSrc);
57
58 return 0;
59 }
60
61 /* *
62 * brief Create the graph.
63 * param [in/out] graph: the graph.
64 * [in] isDigraph: Create a digraph when this flag set true.
65 * return none.
66 */
67 void CreateGraph( Graph& graph, bool isDigraph /* = false */ )
68 {
69 cout<<"Create the graph"<<endl;
70 cout<<"Input vertex size:";
71 cin>>graph.mVertexSize;
72
73 cout<<"Input arc size:";
74 cin>>graph.mArcSize;
75
76 // Input vertex
77 for ( int iVertex = 0; iVertex < graph.mVertexSize; iVertex++)
78 {
79 cout<<"Input "<<iVertex+1<<" vertex value:";
80 cin>>graph.mVertex[iVertex];
81 }
82
83 // Initialize adjacency matrix.
84 for ( int i = 0; i < graph.mVertexSize; i++)
85 {
86 for ( int j = 0; j < graph.mVertexSize; j++)
87 {
88 graph.mAdjMatrix[i][j].dWeight = INFINITY;
89 }
90 }
91
92 // Build adjacency matrix.
93 int iInitial = 0;
94 int iTerminal = 0;
95 int xPos = 0;
96 int yPos = 0;
97 double dWeight = 0;
98
99 for ( int k = 0; k < graph.mArcSize; k++)
100 {
101 cout<<"Input "<<k+1<<" arc initial node:";
102 cin>>iInitial;
103
104 cout<<"Input "<<k+1<<" arc terminal node:";
105 cin>>iTerminal;
106
107 cout<<"Input the weight:";
108 cin>>dWeight;
109
110 xPos = LocateVertex(graph, iInitial);
111 yPos = LocateVertex(graph, iTerminal);
112
113 graph.mAdjMatrix[xPos][yPos].dWeight = dWeight;
114
115 if (!isDigraph)
116 {
117 graph.mAdjMatrix[yPos][xPos].dWeight = dWeight;
118 }
119 }
120 }
121
122 /* *
123 * brief Show the weight of the graph arc.
124 * param [in] graph
125 * return none.
126 */
127 void ShowGraph( const Graph& graph)
128 {
129 cout<<"Show the graph represented by adjacency matrix:"<<endl;
130
131 // Output adjacency matrix.
132 for ( int m = 0; m < graph.mVertexSize; m++)
133 {
134 for ( int n = 0; n < graph.mVertexSize; n++)
135 {
136 cout<<graph.mAdjMatrix[m][n].dWeight<<"\t";
137 }
138
139 cout<<endl;
140 }
141 }
142
143 /* *
144 * brief Locate vertex position in the adjacency matrix.
145 * param [in] graph:
146 * [in] vertex:
147 * return The position of the vertex. If not found return -1.
148 */
149 int LocateVertex( const Graph& graph, int vertex )
150 {
151 for ( int i = 0; i < graph.mVertexSize; i++)
152 {
153 if (graph.mVertex[i] == vertex)
154 {
155 return i;
156 }
157 }
158
159 return -1;
160 }
161
162 /* *
163 * brief Dijkstra algorithm to find the shortest path.
164 * param [in] graph.
165 * [in] source node.
166 * return none.
167 */
168 void Dijkstra( const Graph& graph, int src )
169 {
170 int iMin = 0;
171 double dMin = 0;
172 double dTempMin = 0;
173
174 // The distance between source node to the vi node.
175 double dDist[VERTEX_NUM] = {0};
176
177 // The set of all the shortest path node.
178 bool bFinalSet[VERTEX_NUM] = { false};
179
180 // Initialize status: if there is an arc between
181 // source node and vi node, set the distance to
182 // its weight value.
183 for ( int i = 0; i < graph.mVertexSize; i++)
184 {
185 bFinalSet[i] = false;
186
187 dDist[i] = graph.mAdjMatrix[src][i].dWeight;
188 }
189
190 // Mark the visit flag.
191 dDist[src] = 0;
192 bFinalSet[src] = true;
193
194 // Dijstra algorithm: other N-1 vertex.
195 for ( int j = 1; j < graph.mVertexSize; j++)
196 {
197 // Find a vertex that its distance is the shortest
198 // to the source node.
199 dMin = INFINITY;
200
201 for ( int k = 0; k < graph.mVertexSize; k++)
202 {
203 if ((!bFinalSet[k]) && (dDist[k] <= dMin))
204 {
205 iMin = k;
206 dMin = dDist[k];
207 }
208 }
209
210 // Add the nearest vertex to the final set.
211 bFinalSet[iMin] = true;
212
213 // Output the shortest path vertex and its distance.
214 cout<<"The shortest path between "<<src<<" and "<<iMin<<" is: "<<dMin<<endl;
215
216 // Update the shortest path.
217 for ( int l = 0; l < graph.mVertexSize; l++)
218 {
219 dTempMin = dMin + graph.mAdjMatrix[iMin][l].dWeight;
220
221 if ((!bFinalSet[l]) && (dTempMin < dDist[l]))
222 {
223 dDist[l] = dTempMin;
224 }
225 }
226 }
227 }
228
以图
1为例，程序运行结果如下所示：
2 * Copyright (c) 2013 eryar All Rights Reserved.
3 *
4 * File : Main.cpp
5 * Author : eryar@163.com
6 * Date : 2013-1-1 16:50
7 * Version : 0.1v
8 *
9 * Description : Use adjacency matrix of a graph.
10 * Use Dijkstra method to find the shortest path.
11 *
12 */
13
14 #include <CFLOAT>
15 #include <IOSTREAM>
16 using namespace std;
17
18 const int VERTEX_NUM = 20;
19 const double INFINITY = DBL_MAX;
20
21 // Arc of the graph.
22 typedef struct SArc
23 {
24 double dWeight;
25 }AdjMatrix[VERTEX_NUM][VERTEX_NUM];
26
27 // The graph: include vertex size and
28 // arc size also the adjacency matrix.
29 typedef struct SGraph
30 {
31 int mVertexSize;
32 int mArcSize;
33 int mVertex[VERTEX_NUM];
34 AdjMatrix mAdjMatrix;
35 }Graph;
36
37 // Function declarations.
38 void CreateGraph(Graph& graph, bool isDigraph = false);
39 int LocateVertex( const Graph& graph, int vertex);
40 void ShowGraph( const Graph& graph);
41 void Dijkstra( const Graph& graph, int src);
42
43 // Main function.
44 int main( int argc, char* argv[])
45 {
46 Graph graph;
47 int iSrc = 0;
48
49 CreateGraph(graph, true);
50
51 ShowGraph(graph);
52
53 cout<<"Input the source node of the shortest path:";
54 cin>>iSrc;
55
56 Dijkstra(graph, iSrc);
57
58 return 0;
59 }
60
61 /* *
62 * brief Create the graph.
63 * param [in/out] graph: the graph.
64 * [in] isDigraph: Create a digraph when this flag set true.
65 * return none.
66 */
67 void CreateGraph( Graph& graph, bool isDigraph /* = false */ )
68 {
69 cout<<"Create the graph"<<endl;
70 cout<<"Input vertex size:";
71 cin>>graph.mVertexSize;
72
73 cout<<"Input arc size:";
74 cin>>graph.mArcSize;
75
76 // Input vertex
77 for ( int iVertex = 0; iVertex < graph.mVertexSize; iVertex++)
78 {
79 cout<<"Input "<<iVertex+1<<" vertex value:";
80 cin>>graph.mVertex[iVertex];
81 }
82
83 // Initialize adjacency matrix.
84 for ( int i = 0; i < graph.mVertexSize; i++)
85 {
86 for ( int j = 0; j < graph.mVertexSize; j++)
87 {
88 graph.mAdjMatrix[i][j].dWeight = INFINITY;
89 }
90 }
91
92 // Build adjacency matrix.
93 int iInitial = 0;
94 int iTerminal = 0;
95 int xPos = 0;
96 int yPos = 0;
97 double dWeight = 0;
98
99 for ( int k = 0; k < graph.mArcSize; k++)
100 {
101 cout<<"Input "<<k+1<<" arc initial node:";
102 cin>>iInitial;
103
104 cout<<"Input "<<k+1<<" arc terminal node:";
105 cin>>iTerminal;
106
107 cout<<"Input the weight:";
108 cin>>dWeight;
109
110 xPos = LocateVertex(graph, iInitial);
111 yPos = LocateVertex(graph, iTerminal);
112
113 graph.mAdjMatrix[xPos][yPos].dWeight = dWeight;
114
115 if (!isDigraph)
116 {
117 graph.mAdjMatrix[yPos][xPos].dWeight = dWeight;
118 }
119 }
120 }
121
122 /* *
123 * brief Show the weight of the graph arc.
124 * param [in] graph
125 * return none.
126 */
127 void ShowGraph( const Graph& graph)
128 {
129 cout<<"Show the graph represented by adjacency matrix:"<<endl;
130
131 // Output adjacency matrix.
132 for ( int m = 0; m < graph.mVertexSize; m++)
133 {
134 for ( int n = 0; n < graph.mVertexSize; n++)
135 {
136 cout<<graph.mAdjMatrix[m][n].dWeight<<"\t";
137 }
138
139 cout<<endl;
140 }
141 }
142
143 /* *
144 * brief Locate vertex position in the adjacency matrix.
145 * param [in] graph:
146 * [in] vertex:
147 * return The position of the vertex. If not found return -1.
148 */
149 int LocateVertex( const Graph& graph, int vertex )
150 {
151 for ( int i = 0; i < graph.mVertexSize; i++)
152 {
153 if (graph.mVertex[i] == vertex)
154 {
155 return i;
156 }
157 }
158
159 return -1;
160 }
161
162 /* *
163 * brief Dijkstra algorithm to find the shortest path.
164 * param [in] graph.
165 * [in] source node.
166 * return none.
167 */
168 void Dijkstra( const Graph& graph, int src )
169 {
170 int iMin = 0;
171 double dMin = 0;
172 double dTempMin = 0;
173
174 // The distance between source node to the vi node.
175 double dDist[VERTEX_NUM] = {0};
176
177 // The set of all the shortest path node.
178 bool bFinalSet[VERTEX_NUM] = { false};
179
180 // Initialize status: if there is an arc between
181 // source node and vi node, set the distance to
182 // its weight value.
183 for ( int i = 0; i < graph.mVertexSize; i++)
184 {
185 bFinalSet[i] = false;
186
187 dDist[i] = graph.mAdjMatrix[src][i].dWeight;
188 }
189
190 // Mark the visit flag.
191 dDist[src] = 0;
192 bFinalSet[src] = true;
193
194 // Dijstra algorithm: other N-1 vertex.
195 for ( int j = 1; j < graph.mVertexSize; j++)
196 {
197 // Find a vertex that its distance is the shortest
198 // to the source node.
199 dMin = INFINITY;
200
201 for ( int k = 0; k < graph.mVertexSize; k++)
202 {
203 if ((!bFinalSet[k]) && (dDist[k] <= dMin))
204 {
205 iMin = k;
206 dMin = dDist[k];
207 }
208 }
209
210 // Add the nearest vertex to the final set.
211 bFinalSet[iMin] = true;
212
213 // Output the shortest path vertex and its distance.
214 cout<<"The shortest path between "<<src<<" and "<<iMin<<" is: "<<dMin<<endl;
215
216 // Update the shortest path.
217 for ( int l = 0; l < graph.mVertexSize; l++)
218 {
219 dTempMin = dMin + graph.mAdjMatrix[iMin][l].dWeight;
220
221 if ((!bFinalSet[l]) && (dTempMin < dDist[l]))
222 {
223 dDist[l] = dTempMin;
224 }
225 }
226 }
227 }
228
1: Create the graph
2: Input vertex size:6
3: Input arc size:8
4: Input 1 vertex value:0
5: Input 2 vertex value:1
6: Input 3 vertex value:2
7: Input 4 vertex value:3
8: Input 5 vertex value:4
9: Input 6 vertex value:5
10: Input 1 arc initial node:0
11: Input 1 arc terminal node:2
12: Input the weight:10
13: Input 2 arc initial node:0
14: Input 2 arc terminal node:4
15: Input the weight:30
16: Input 3 arc initial node:0
17: Input 3 arc terminal node:5
18: Input the weight:100
19: Input 4 arc initial node:1
20: Input 4 arc terminal node:2
21: Input the weight:5
22: Input 5 arc initial node:2
23: Input 5 arc terminal node:3
24: Input the weight:50
25: Input 6 arc initial node:3
26: Input 6 arc terminal node:5
27: Input the weight:10
28: Input 7 arc initial node:4
29: Input 7 arc terminal node:3
30: Input the weight:20
31: Input 8 arc initial node:4
32: Input 8 arc terminal node:5
33: Input the weight:60
34: Show the graph represented by adjacency matrix:
35: 1.79769e+308 1.79769e+308 10 1.79769e+308 30 100
36: 1.79769e+308 1.79769e+308 5 1.79769e+308 1.79769e+308 1.79769e+308
37: 1.79769e+308 1.79769e+308 1.79769e+308 50 1.79769e+308 1.79769e+308
38: 1.79769e+308 1.79769e+308 1.79769e+308 1.79769e+308 1.79769e+308 10
39: 1.79769e+308 1.79769e+308 1.79769e+308 20 1.79769e+308 60
40: 1.79769e+308 1.79769e+308 1.79769e+308 1.79769e+308 1.79769e+308 1.79769e+308
41: Input the source node of the shortest path:0
42: The shortest path between 0 and 2 is: 10
43: The shortest path between 0 and 4 is: 30
44: The shortest path between 0 and 3 is: 50
45: The shortest path between 0 and 5 is: 60
46: The shortest path between 0 and 1 is: 1.79769e+308
47: Press any key to continue
四、结论 Conclusion
程序运行结果表明，从源点到其余各顶点的最短路径是依路径长度递增的序列。若要想求从源点到指定终点的最短路径，运行Dijkstra算法时到指定终点即可结束。
五、参考资料
1. Wiki地址:http://en.wikipedia.org/wiki/Dijkstra's_algorithm
2. 具体讲解请看视频：http://video.sina.com.cn/v/b/79074990-1298777923.html
3. 严蔚敏、吴伟民 数据结构（C语言版） 清华大学出版社
