不忘初心,
牢记使命。

最短路径算法(迪杰斯特拉算法和弗洛伊德算法)

2021-04-01 大聪明 0评论 233 0喜欢

最短路径算法(迪杰斯特拉算法和弗洛伊德算法)

迪杰斯特拉算法

在一个带权值的图G中,给定一个源点V,求从V出发到图G中其余各个顶点的最短路径问题。

例如在下边这张图中从顶点1出发,到各个顶点间的最短路径。

img

首先一个S集合记录已经找到的距离顶点1的最短路径的顶点,dis[i]表示从顶点1到顶点i之间的最短距离。

S = {1,}

S\顶点 2 3 4 5 6 7 8
{1,5,} 3 2 1
S = {1,5,3,} 3 2 5 4
S = {1,5,3,2,} 3 3 5 4
S = {1,5,3,2,4,} 3 5 5 4
S = {1,5,3,2,4,8,} 5 5 4
S = {1,5,3,2,4,8,6,} 5 5
S = {1,5,3,2,4,8,6,7} 5

得到 dis=[0, 3, 2, 3, 1, 5, 5, 4],所以从顶点1出发到顶点1 2 3 4 5 6 7 8的最短距离分别为0, 3, 2, 3, 1, 5, 5, 4。

具体步骤

首先;S = {1,}

第一步:

找出所有顶点与1的距离,无法到达即为∞,见上表第二行。中出最小的数对应的顶点,即为距离顶点1最短的顶点,为5,加入集合S。

S = {1,5}

第二步:

从5开始出发,找到1->5->所有其他顶点间的最短距离,如果比原先记录的数值小就更新,否则不变。

例如顶点6,开始1到6是为∞,现在由1->5->6为5,所以更新为5.

如果1->5->顶点 不可达,则还是为原先的值不要变。

找到最小值2对应的顶点为3,加入已找到的最短距离的顶点集合中

S = {1,5,3}

第三步:

从顶点3开始出发,同理。说i一下顶点6,1->3->6距离为6,此前已有距离5,6>5,所以不更新。

此时由两个最小值,我们任选一个顶点即可。比如选顶点2。

S = {1,5,3,2,}

接下来

S = {1,5,3,2,4}

S = {1,5,3,2,4,8,}

S = {1,5,3,2,4,8,6,}

S = {1,5,3,2,4,8,6,7}

dis=[0, 3, 2, 3, 1, 5, 5, 4]

练习题

给定一个如上所示的图,图中的边代表了两个节点间的距离,如果使用迪杰斯特拉算法对节点1和节点8求最短路径,则当完成计算时,算得节点1到节点8的最短路径是?同时当完成节点1到节点8的最短路径计算时,节点1到哪些节点(除了1和8)的最短路径也已经计算完毕?

A. 最短路径:4;已经算得最短的节点:5

B. 最短路径:4;已经算得最短路的节点:2,3,4,5

C. 最短路径:4;已经算得最短路的节点:5,6

D. 最短路径:7;已经算得最短路的节点:3,5,6

参考答案(B)

解析:在找到顶点8的最短距离时S = {1,5,3,2,4,8,},上表第六行可知,所以知道最短距离为4。已经算得最短路的节点:2,3,4,5除啦1,8 。

python代码实现

待补

弗洛伊德算法

发表评论 取消回复

电子邮件地址不会被公开。

请输入正确格式的qq邮箱
请输入以http或https开头的URL,格式如:https://libo_sober.top