与贝尔曼福特算法一样，狄克斯特拉算法也是求解最短路径问题的算法，使用它可以求得从起点到终点的路径中权重总和最小的那条路径。
new.jpg
直接上步骤：
这里设A为起点，G为搜索终点，进行迪克斯特拉算法操作
首先设置每个顶点的初始权重
起点A 权重为0.其他顶点权重为+∞
A 0
B 2
C 5
D +∞
E +∞
F +∞
G +∞
从A点出发，寻找当前顶点可以直达，并且没有被搜索过的顶点。
此处是顶点B和顶点C，B和C作为候补顶点
求出顶点B和顶点C的权重
顶点B的权重计算为订单A的权重加上A-B路径权重。
顶点C的权重计算为顶点A的权重加上A-C路径权重。
B顶点权重 = 0 + 2 = 2 < +∞
更新B顶点权重
C顶点权重 = 0 + 5 = 5 < +∞
更新C顶点权重
A 0
B 2 A - B
C 5 A - C
D +∞
E +∞
F +∞
G +∞
从候补顶点中选出权重较小的一个顶点继续进行搜索。
这里选择B顶点进行下一步搜索。
此时顶点E、顶点D、顶点C为候补顶点
求出顶点E、顶点D、顶点C的权重
E顶点的权重等于B顶点的权重 + 顶点B到顶点E的路径距离 = 2 + 3 = 5 < +∞ 更新 A - B - E
D顶点的权重等于B顶点的权重 + 顶点B到顶点D的路径距离 = 2 + 1 = 3 < +∞ 更新 A - B - D
顶点C的权重等于B顶点的权重 + 顶点B到顶点C的路径距离 = 2 + 6 = 8 > 5 不更新 A - C
A 0
B 2 A - B
C 5 A - C
D 3 A - B - E
E 5 A - B - E
F +∞
G +∞
此时找出候补顶点中权重最小的顶点D,从D开始进行新的一次搜索
D可连接的顶点是B和E
从D求出B和E的权重
B顶点权重= 顶点D权重 + D到B的路径距离 = 3 + 1 = 4 > 2 不更新
E顶点的权重 = 顶点D权重 + 顶点D到顶点E的路径距离 = 3 + 4 = 7 > 5 不更新
A 0
B 2 A - B
C 5 A - C
D 3 A - B - E
E 5 A - B - E
F +∞
G +∞
现在两个顶点C和E，权重相等，选择哪一个进行下一步都可以，这里选择C
这里用C求F的权重，F权重被更新为13
A 0
B 2 A - B
C 5 A - C
D 3 A - B - E
E 5 A - B - E
F 13 A - C - F
G +∞
此时比较F和E的权重，E权重较小，从E开始继续搜索
用E求出G的权重是14
A 0
B 2 A - B
C 5 A - C
D 3 A - B - E
E 5 A - B - E
F 13 A - C - F
G 14 A - B - E - G
此时比较F和G，F权重较小，求得G权重大于14，不更新，整图搜索完毕。
求得A-G权重是14，最短路径是A - B - E - G.
网友评论