对于如下赋权图,利用Dijkstra算法求解顶点0到其它顶点的最短路的距离及路径,其中图的条边用a到p字母表示,字母旁边的数字为该边所对应的的权值
时间: 2024-04-25 20:27:12 浏览: 118
PHP实现的迪科斯彻(Dijkstra)最短路径算法实例
根据Dijkstra算法,需要维护一个集合S,表示已经找到最短路的点,以及一个数组dist,表示源点到其他点的距离。初始化时,S中只包含源点0,dist数组中除了源点0的位置为0,其余位置均为无穷大。
接下来,每次从dist数组中选择一个最小值对应的点v,将其加入集合S中,并更新与v相邻的点的距离。重复这个过程,直到S中包含所有点。
具体步骤如下:
1. 初始状态:
S = {0}
dist = [0, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf]
2. 选取距离源点0最近的点1,并更新与1相邻的点的距离:
S = {0, 1}
dist = [0, 5, 7, 8, inf, 9, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf]
3. 选取距离源点0和1最近的点2,并更新与2相邻的点的距离:
S = {0, 1, 2}
dist = [0, 5, 7, 8, 10, 9, 12, 14, 18, inf, inf, inf, inf, inf, inf, inf]
4. 选取距离源点0、1和2最近的点5,并更新与5相邻的点的距离:
S = {0, 1, 2, 5}
dist = [0, 5, 7, 8, 10, 9, 11, 14, 18, inf, inf, inf, inf, inf, inf, inf]
5. 选取距离源点0、1、2和5最近的点3,并更新与3相邻的点的距离:
S = {0, 1, 2, 5, 3}
dist = [0, 5, 7, 8, 10, 9, 11, 13, 15, inf, inf, inf, inf, inf, inf, inf]
6. 选取距离源点0、1、2、5和3最近的点6,并更新与6相邻的点的距离:
S = {0, 1, 2, 5, 3, 6}
dist = [0, 5, 7, 8, 10, 9, 11, 13, 15, 19, 23, 26, 28, 30, inf, inf]
7. 选取距离源点0、1、2、5、3和6最近的点4,并更新与4相邻的点的距离:
S = {0, 1, 2, 5, 3, 6, 4}
dist = [0, 5, 7, 8, 10, 9, 11, 13, 15, 19, 23, 26, 28, 30, 31, inf]
8. 选取距离源点0、1、2、5、3、6和4最近的点7,并更新与7相邻的点的距离:
S = {0, 1, 2, 5, 3, 6, 4, 7}
dist = [0, 5, 7, 8, 10, 9, 11, 13, 15, 19, 23, 26, 28, 30, 31, 34]
9. 选取距离源点0、1、2、5、3、6、4和7最近的点8,并更新与8相邻的点的距离:
S = {0, 1, 2, 5, 3, 6, 4, 7, 8}
dist = [0, 5, 7, 8, 10, 9, 11, 13, 15, 19, 23, 26, 28, 30, 31, 34]
最终得到源点0到其他点的最短路距离为:
dist = [0, 5, 7, 8, 10, 9, 11, 13, 15, 19, 23, 26, 28, 30, 31, 34]
其中,dist[1]表示源点0到顶点1的最短路距离为5,dist[2]表示源点0到顶点2的最短路距离为7,以此类推。
路径可以根据更新dist数组时记录的前驱节点得到,具体方法可参考Dijkstra算法的实现。
阅读全文