带权图的最短路径问题

1、带权图的最短路径问题/course_ware/data_structure/web/tu/tu7.5.1.htm1、带权图的最短路径问题 带权图的最短路径问题即求两个顶点间长度最短的路径。其中：路径长度不是指路径上边数的总和，而是指路径上各边的权值总和。 路径长度的的具体含义取决于边上权值所代表的意义。【例】交通网络中常常提出的如下问题就是带权图中求最短路径的问题。 （1）两地之间是否有路相通? （2）在有多条通路的情况下，哪一条最短?其中:交通网络可以用带权图表示：图中顶点表示城镇，边表示两个城镇之间的道路，边上的权值可表示两城镇间的距离，交通费用或途中所需的时间等等。2、交通网络的表示 由

2、于交通网络存在有向性，所以一般以有向网络表示交通网络。【例】设A城到B城有一条公路，A城的海拔高于B城。若考虑到上坡和下坡的车速不同，则边和边上表示行驶时间的权值也不同。即和应该是两条不同的边。3、源点和终点 习惯上称路径的开始顶点为源点(Source)，路径的最后一个顶点为终点(Destination)。 为了讨论方便，设顶点集V=0，1，n-1，并假定所有边上的权值均是表示长度的非负实数。单源最短路径问题(Single-Source Shortest-PathsProblem) 单源最短路径问题：已知有向带权图(简称有向网)G=(V，E)，找出从某个源点sV到V中其余各顶点的最短路径。1、

3、边上权值相等的有向网的单源最短路径 用求指定源点的BFS生成树的算法可解决2、迪杰斯特拉(Dijkstra)算法求单源最短路径 由Dijkstra提出的一种按路径长度递增序产生各顶点最短路径的算法。（1）按路径长度递增序产生各顶点最短路径 若按长度递增的次序生成从源点s到其它顶点的最短路径，则当前正在生成的最短路径上除终点以外，其余顶点的最短路径均已生成（将源点的最短路径看作是已生成的源点到其自身的长度为0的路径）。【例】在有向网G8中，假定以顶点0为源点，则它则其余各顶点的最短路径按路径递增序排列如右表所示（2）算法基本思想 设S为最短距离已确定的顶点集（看作红点集），V-S是最短距离尚未确

4、定的顶点集（看作蓝点集）。初始化 初始化时，只有源点s的最短距离是已知的(SD(s)=0)，故红点集S=s，蓝点集为空。重复以下工作，按路径长度递增次序产生各顶点最短路径 在当前蓝点集中选择一个最短距离最小的蓝点来扩充红点集，以保证算法按路径长度递增的次序产生各顶点的最短路径。 当蓝点集中仅剩下最短距离为的蓝点，或者所有蓝点已扩充到红点集时，s到所有顶点的最短路径就求出来了。 注意： 若从源点到蓝点的路径不存在，则可假设该蓝点的最短路径是一条长度为无穷大的虚拟路径。 从源点s到终点v的最短路径简称为v的最短路径；s到v的最短路径长度简称为v的最短距离，并记为SD(v)。（3）在蓝点集中选择一个

5、最短距离最小的蓝点k来扩充红点集 根据按长度递增序产生最短路径的思想，当前最短距离最小的蓝点k的最短路径是： 源点，红点1，红点2，红点n，蓝点k距离为：源点到红点n最短距离+边长 为求解方便，设置一个向量D0n-1，对于每个蓝点v V-S，用Dv记录从源点s到达v且除v外中间不经过任何蓝点(若有中间点，则必为红点)的最短路径长度（简称估计距离）。 若k是蓝点集中估计距离最小的顶点，则k的估计距离就是最短距离，即若Dk=minDi iV-S，则Dk=SD(k)。 初始时，每个蓝点v的Dc值应为权w，且从s到v的路径上没有中间点，因为该路径仅含一条边。 注意： 在蓝点集中选择一个最短距离最小的蓝

6、点k来扩充红点集是Dijkstra算法的关键 （4）k扩充红点集s后，蓝点集估计距离的修改 将k扩充到红点后，剩余蓝点集的估计距离可能由于增加了新红点k而减小，此时必须调整相应蓝点的估计距离。 对于任意的蓝点j，若k由蓝变红后使Dj变小，则必定是由于存在一条从s到j且包含新红点k的更短路径：P=。且Dj减小的新路径P只可能是由于路径和边组成。 所以，当length(P)=Dk+w小于Dj时，应该用P的长度来修改Dj的值。（5）Dijkstra算法Dijkstra(G，D，s) /用Dijkstra算法求有向网G的源点s到各顶点的最短路径长度 /以下是初始化操作 S=s；Ds=0； /设置初始的

7、红点集及最短距离 for( all i V-S )do /对蓝点集中每个顶点i Di=Gsi； /设置i初始的估计距离为w /以下是扩充红点集 for(i=0;iDk+Gkj) /新红点k使原Dj值变小时，用新路径的长度修改Dj， /使j离s更近。 Dj=Dk+Gkj； 【例】对有向网G8以0为源点执行上述算法的过程及红点集、k和D向量的变化见【 HYPERLINK 动画.swf 参见动画演示】。（6）保存最短路径的Dijkstra算法 设置记录顶点双亲的向量P0n-1保存最短路径：当顶点i无双亲时，令Pi=-1。 当算法结束时，可从任一Pi反复上溯至根(源点)求得顶点i的最短路径，只不过路径

8、方向正好与从s到i的路径相反。 具体的求精算法【参见教材】 。 Dijkstra算法的时间复杂度为O(n2)其他最短路径问题 最短路径问题的提法很多，其它的最短路径问题均可用单源最短路径算法予以解决：单目标最短路径问题(Single-Destination Shortest-Paths Problem)：找出图中每一顶点v到某指定顶点u的最短路径。只需将图中每条边反向，就可将这一问题变为单源最短路径问题，单目标u变为单源点u。单顶点对间最短路径问题(Single-Pair Shortest-Path Problem)：对于某对顶点u和v，找出从u到v的一条最短路径。显然，若解决了以u为源点的单源最短路径问题，则上述问题亦迎刃而