5.6 最短路径★3◎4

5.6 最短路径★3◎4


5.6 最短路径★3◎4
  在带权图中,一条路径上各边的权值总和称为“路径长度”, 两个顶点间长度最短的路径称为&ld…

5.6 最短路径★3◎4

5.6 最短路径★3◎4

  在带权图中,一条路径上各边的权值总和称为“路径长度”, 两个顶点间长度最短的路径称为“最短路径”
  最短路径问题在实际中应用很广泛,比如交通网络:图中顶点表示城镇,边表示两个城镇之间的道路,边上的权值可表示两城镇间的距离,求两个城镇之间的最短距离就是带权图中两个顶点之间的最短路径。
  在带权图中,习惯上我们称路径开始的顶点为“源点”,路径的最后一个顶点为“终点”
  1.求单个顶点到其他顶点的最短路径
  (1)问题提出
  已知有向带权图(简称有向网)G=(V, E),找出从某个源点s∈V到V中其余各顶点的最短路径。
  (2)迪杰斯特拉(Dijkstra)算法基本思想
  设S为最短距离已确定的顶点集,则V-S是最短距离尚未确定的顶点集,增加一个辅助向量D,它的每个分量D[i]表示当前已知的从源点s到终点Vi的最短路径长度。
  ①算法开始时,只有源点s的最短距离是已知的(D[s]=0),此时已确定顶点集S={s},同时向量D的每个分量取值可以从邻接矩阵A中获得。
  ②针对每一个Vi∈V-S,重新计算源点S到终点Vi的最短路径长度D[i],计算方法如下:
  假设新加入集合S的顶点为Vj,如果D[j]+A[j,i]<D[i],则将D[i]赋值为D[j]+A[j,i],并记下此路径。
  ③在集合V-S的所有顶点中,选取一个距离S点路径长度最短的,将此顶点加入集合S中。
  ④重复执行步骤②和③,直到集合V-S为空,或者集合V-S中所有顶点距离S的路径长度为无穷大时结束。
  (3)算法实例
  用迪杰斯特拉算法求图5-12(a)的顶点V0到其他顶点的最短路径长度。

  初始时S为{V0},D[0]=0,其余步骤如表5-7所示。

表5-7 迪杰斯特拉算法求V0到其他顶点最短路径步骤

集  合  S 向  量  D 分    析
V0 V1 V2 V3 V4 V5  
V0 10 30 100 集合V-S中顶点V2对应数值最小,所以V2入S
V0,V2 10 60 30 100 ①集合V-S中顶点V4对应数值最小,所以V4入S
V0,V2,V4 10 50 30 90 ②集合V-S中顶点V3对应数值最小,所以V3入S
V0,V2,V4,V3 10 50 30 60 ③集合V-S中顶点V5对应数值最小,所以V5入S
V0,V2,V4,V3,V5 10 50 30 60 集合V-S中顶点到S的最短路径长度均为∞,算法结束,向量D即为所求。

  分析:
  ① S集合中新加入顶点V2
  顶点V1
  分析V2:A[2,1]为∞,D[1]取值不变
  顶点V3:
  分析V2:D[2]+A[2,3]=10+50=60 < D[3]=∞,所以D[3]=60
  顶点V4:
  分析V2:A[2,4]为∞,D[4]取值不变
  顶点V5:
  分析V2:A[2,5]为∞,D[4]取值不变
  ② S集合中新加入顶点V4
  顶点V1:
  分析V4:A[4,1]为∞,D[1]取值不变
  顶点V3:
  分析V4:D[4]+A[4,3]=30+20=50 < D[3]=60;所以D[3]=50
  顶点V5:
  分析V4:D[4]+A[4,5]=30+60=90 < D[5]=100;所以D[5]=90
  ③ S集合中新加入顶点V3
  顶点V1:
  分析V3:A[3,1]为∞,D[1]取值不变
  顶点V5:
  分析V3:D[3]+A[3,5]=50+10=60 < D[5]=90;所以D[5]=60
  综上,求解顶点V0到其他顶点的最短路径的步骤、最短路径顶点序列和路径长度如表5-8所示。

表5-8 从顶点V0到各终点的D值和最短路径求解过程

  第1步 第2步 第3步 第4步
  距离 路径 距离 路径 距离 路径 距离 路径
V0 0   0   0   0  
V1        
V2 10 V0,V2 10 V0,V2 10 V0,V2 10 V0,V2

续表

  第1步 第2步 第3步 第4步
  距离 路径 距离 路径 距离 路径 距离 路径
V3   60 V0,V2,V3 50 V0,V4,V3 50 V0,V4,V3
V4 30 V0,V4 30 V0,V4 30 V0,V4 30 V0,V4
V5 100 V0,V5 100 V0,V5 90 V0,V4,V5 60 V0,V4,V3,V5

(4)算法分析
此算法的时间复杂度为O( )。
2.求每一对顶点之间的最短路径
对每一个顶点都调用一次迪杰斯特拉算法,即可得出每一个顶点之间的最短路径,此时算法的时间复杂度为O( )。

5.6 最短路径★3◎4

    关于作者: admin

    这里可以再内容模板定义一些文字和说明,也可以调用对应作者的简介!或者做一些网站的描述之类的文字活着HTML!

    为您推荐

    发表评论

    电子邮件地址不会被公开。 必填项已用*标注

    评论列表 人参与

    联系我们

    联系我们

    8888-88888888

    在线咨询: QQ交谈

    邮箱: email@admin.com

    工作时间:周一至周五,9:00-17:30,节假日休息

    关注微信
    微信扫一扫关注我们

    微信扫一扫关注我们

    关注微博
    返回顶部