数据结构基础之最短路径贪心算法

ゝ一世哀愁。 2022-08-21 05:39 200阅读 0赞

Dijkstra算法是解单源最短路径问题的贪心算法。其基本思想是，设置顶点集合点集合S并不断地做贪心选择来扩充这个集合。一个顶点属于集合S当且仅当从源到该顶点的最短路径长度已知。初始时，S中仅含有源。设u是G的其一顶点。把从源到u且中间只经过S中顶点的路称为从源到u的特殊路径，并用数组Distance记录当前每个顶点所对应的最短特殊路径长度。Dijkstra算法每次从V-S中取出具有最短特殊路长度的顶占，Distance就记录了从源到所有其它顶点之间最短路径长度。

例如下图中的有向图，应用Dijkstra算法计算从源顶点1到其它顶点最短路径的过程列表在下表中。

![20140809115112875][]

![20140809115322915][]

算法过程描述：  
表格中默认选取的起始顶点为1顶点，所以本问题就转化为求解1顶点到2, 3, 4, 5这几个顶点的最短路径。首先初始条件列出1顶点到2, 3, 4, 5各个顶点的距离，这个距离直接在图的存储邻接矩阵中得到，选取距离最近的一个也就是2顶点加入集合S，下面要进行的是比较关键的一步，这个时候应该去获取3, 4, 5三个顶点到集合S的最短距离(从1顶点出发，可以经过S中的任意顶点)：将1到2顶点的距离加上2到各个点的距离，然后用这个距离来同1到各个顶点的距离相比较，谁小就取谁，以此类推，然后每次取Distance\[\]最小的值进入集合S。  
这样下去，Distance\[\]中存放的就是每个顶点到集合S的最短距离，比如当前的集合只有1, 2，按照规则顶点4应该入选进集合S，因为Distance\[3\]没有入选集合的顶点中对应的Distance\[\]最小的顶点。现在需要计算3和5到新集合S=\{1, 2, 4\}的最短距离，这个时候就只需要将Distance\[2\]和Distance\[4\]中的值（现在这里面的值表示集合S=\{1, 2\}到顶点3和5顶点的最短距离），但是现在集合中加入了顶点4，怎么计算？计算方法如下：  
Distance\[3\] + 邻接矩阵中顶点4到顶点3的距离 < Distance\[2\] ?  
Distance\[3\]：(顶点4到S=\{1, 2\}的最短距离)  
Distance\[2\]: (顶点3到S=\{1, 2\}的最短距离)  
如果这个小于成立，那么很明显新的集合到顶点3的最小距离应该是先从S=\{1, 2\}到顶点4的最短距离，然后再从顶点4到顶点3。

由于每一次的比较都是在上一次集合的最优结果中计算的，所以新计算出来的顶点3到集合S=\{1, 2, 4\}的最短距离也是全局最优的。

对应的C语言代码如下：

**\[objc\]** [view plain][] [copy][view plain]

[![在CODE上查看代码片][CODE]][CODE_CODE] [![派生到我的代码片][ico_fork.svg]][ico_fork.svg 1]

1.  \#include <stdio.h>
2.  
3.  \#define M 65535 //无穷大
4.  \#define N 5 //顶点数
5.  
6.  //Dijkstra算法函数，求给定顶点到其余各点的最短路径
7.  //参数：邻接矩阵、出发点的下标、结果数组、路径前一点记录
8.  **void** Dijkstra(**int** Cost\[\]\[N\], **int** v0, **int** Distance\[\], **int** prev\[\]) 
9.  \{ 
10. **int** s\[N\]; 
11. **int** mindis,dis; 
12. **int** i, j, u; 
13. //初始化
14. **for**(i=0; i<N; i++) 
15.  \{ 
16.  Distance\[i\] = Cost\[v0\]\[i\]; 
17.  s\[i\] = 0; 
18. **if**(Distance\[i\] == M) 
19.  prev\[i\] = -1; 
20. **else**
21.  prev\[i\] = v0; 
22.  \} 
23.  Distance\[v0\] = 0; 
24.  s\[v0\] = 1; //标记v0
25. //在当前还未找到最短路径的顶点中，
26. //寻找具有最短距离的顶点
27. **for**(i=1; i < N; i++) 
28.  \{ //每循环一次，求得一个最短路径
29.  mindis = M; 
30.  u = v0; 
31. **for** (j=0; j < N; j++) //求离出发点最近的顶点
32. **if**(s\[j\]==0 && Distance\[j\]<mindis) 
33.  \{ 
34.  mindis = Distance \[j\]; 
35.  u = j; 
36.  \} // if语句体结束，j循环结束
37.  s\[u\] = 1; 
38. **for**(j=0; j<N; j++) //修改递增路径序列（集合）
39. **if**(s\[j\]==0 && Cost\[u\]\[j\]<M) 
40.  \{ //对还未求得最短路径的顶点
41. //求出由最近的顶点 直达各顶点的距离
42.  dis = Distance\[u\] +Cost\[u\]\[j\]; 
43. // 如果新的路径更短，就替换掉原路径
44. 
45. **if**(Distance\[j\] > dis) 
46.  \{ 
47.  Distance\[j\] = dis; 
48.  prev\[j\] = u; 
49.  \} 
50.  \} // if 语句体结束，j循环结束
51.  \} // i循环结束
52. \} 
53. // 输出最短路径
54. // 参数：路径前一点记录、出发点的下标、到达点下标
55. **void** PrintPrev(**int** prev\[\],**int** v0,**int** vn) 
56. \{ 
57. **int** tmp = vn; 
58. **int** i, j; 
59. //临时存路径
60. **int** tmpprv\[N\]; 
61. //初始化数组
62. **for**(i=0; i < N; i++) 
63.  tmpprv\[i\] = 0; 
64. 
65. //记录到达点下标
66.  tmpprv\[0\] = vn+1; 
67. //中间点用循环记录
68. **for**(i =0, j=1; j < N ;j++) 
69.  \{ 
70. **if**(prev\[tmp\]!=-1 && tmp!=0) 
71.  \{ 
72.  tmpprv\[i\] = prev\[tmp\]+1; 
73.  tmp = prev\[tmp\]; 
74.  i++; 
75.  \} 
76. **else****break**; 
77.  \} 
78. 
79. //输出路径，数组逆向输出
80. **for**(i=N-1; i >= 0; i--) 
81.  \{ 
82. **if**(tmpprv\[i\] != 0) 
83.  \{ //排除0元素
84.  printf("V%d", tmpprv\[i\]); 
85. **if**(i) //不是最后一个输出符号 
86.  printf("-->"); 
87.  \} 
88.  \} 
89.  printf("-->V%d", vn+1); 
90. \} 
91. //主函数
92. **int** main() 
93. \{ 
94. //给出有向网的顶点数组
95. **char****char** \*Vertex\[N\]=\{ "V1", "V2", "V3", "V4", "V5"\}; 
96. //给出有向网的邻接矩阵
97. **int** Cost\[N\]\[N\]=\{ 
98.  \{ 0, 10, M, 30, 100\}, 
99.  \{M, 0, 50, M, M\}, 
100.  \{M, M, 0, M, 10\}, 
101.  \{M, M, 20, 0, 60\}, 
102.  \{M, M, M, M, 0\}, 
103.  \}; 
104. **int** Distance\[N\]; //存放求得的最短路径长度
105. **int** prev\[N\]; //存放求得的最短路径
106. **int** i; 
107. //调用Dijkstra算法函数，求顶点V1到其余各点的最短路径
108. //参数：邻接矩阵、顶点数、出发点的下标、 结果数组
109.  Dijkstra(Cost, 0, Distance, prev); 
110. **for**(i=0; i < N; i++) 
111.  \{ 
112. //输出最短路径长度
113.  printf("%s-->%s:%d\\t", Vertex\[0\], Vertex\[i\], Distance\[i\]); 
114. //输出最短路径
115.  PrintPrev(prev, 0, i); 
116.  printf("\\n"); 
117.  \} 
118. 
119. **return**0; 
120. \}

程序运行结果截图：

![20140809115535656][]

[20140809115112875]: /images/20220731/825e930ab2e84a7fa2e12ac55411fe2e.png
[20140809115322915]: /images/20220731/363e90f99b8144d188b9fdae7d5846a3.png
[view plain]: http://blog.csdn.net/laoniu_c/article/details/38455255#
[CODE]: https://code.csdn.net/assets/CODE_ico.png
[CODE_CODE]: https://code.csdn.net/snippets/446492
[ico_fork.svg]: https://code.csdn.net/assets/ico_fork.svg
[ico_fork.svg 1]: https://code.csdn.net/snippets/446492/fork
[20140809115535656]: /images/20220731/eab2c3df2763474d9205ad08476943b0.png