扫码获取更多资源

●单源最短路径

给定有向网G=(V, VR),VR中每一条边＜v;, Vj〉(Vj€V,Vj€V)都有非负的权。指 定V中的一个顶点巧作为源点，寻找从源点巧出发到网中所有其他各顶点的最短路径，这 就是单源最短路径问题(Single-Source Shortest-Paths Problem) o

在图7-37(a)所示的有向网G中，从顶点v0到其余各顶点间的最短路径如图7-37(b) 所示。

从图中可见,从顶点v0到v3有两条不同的路径：(v0, v2, V3)和(Vo, V4 , V3),前者的长度 为60,后者的长度为50,因此后者是从顶点v0到v3的最短路径；而从顶点V。到巧没有路径。

迪杰斯特拉思想

为了求得最短路径，迪杰斯特拉(Dijkstra)提出了一个按路径长度递增的次序产生最短 路径的思想。

(1)求第一条长度最短路径。

引进一个辅助数组dist,它的每个分量dist：i］表示当前所找到的从源点v到每个终点

求下一条长度次最短路径

假设该次最短路径的终点是Vk，则可想而知，这条路径或是(v, vQ,或是(V, Vj, vk)； 它的长度或是从V到vk的弧上的权值，或是dist「j]和从Vj到Vk的弧上的权值之和。

一般情况下，假设S为已求得的最短路径终点的集合，则下一条次最短路径(设其终点 为x)或是弧＜v, X〉,或是中间只经过S中的顶点而最后到达x的路径。

证明：利用反证法证明。

假设此路径上有一个顶点不在S中，则说明存在一条终点不在S而长度比此路径短的 路径，但这是不可能的。因为是按照路径长度递增的次序来产生各个最短路径，所以长度比 此路径短的所有路径均已经产生，它们的终点必定在其中，故假设不成立。

单源最短路径的操作实现

因为在操作过程中，需要快速求得任意两个顶点之间边上的权值，所以在实现单源最短 路径算法时，有向网釆用邻接矩阵存储。

① 设置辅助数组。

• dist[n]：数组分量dist[i]表示当前所找到的从源点v到终点巧的最短路径的长度。 初态：如果从v到V有弧，则dist[i]为弧上的权值；否则设dist[i]为8。

• path[n]：数组分量path[i]是一个串，表示当前所找到的从源点v到终点巧的最短 路径。初态：如果从v到巧有弧，则path[订为”vv『,否则置path[i]为空串。

• final[n]：数组分量final[i]为1且仅当Vi 6 S时，表示已求得从源点v到终点巧的 最短路径。初态：所有数组分量为0。

• s：n]：存放源点和已经生成的终点，表示求得的最短路径终点集合S。初态：只有 一个源点V。

其他最短路径

对给定有向网G=(V, VR)求解最短路径的方法很多，其他最短路径问题均可以采用 单源最短路径算法予以解决。

1.单目标最短路径问题 给定有向网N=(V, VR),VR中每条弧〈巧，Vj〉(Vi£V,Vj€V)都有非负的权。寻找 网中每一个顶点巧到某个指定顶点巧的最短路径，这就是单目标最短路径问题(Single¬Destination Shortest-Paths Problem) o 解决方法：只需将图中每条边反向，就可以将这一问题转化为单源最短路径问题，单目 标Vj变为单源点巧，其算法的时间复杂度也为0(1?)。

2.单顶点对间最短路径问题 给定有向网N=(V, VR),VR中每条弧(Vj£V,Vj€V)都有非负的权。对于 网中某对顶点V和V”找出从巧到巧的一条最短路径，这就是单顶点对间最短路径问题 (Single-Pair Shortest-Path Problem) o 解决方法：显然，如果解决了以Vj为源点的单源最短路径问题，则上述问题也就迎刃而 解了。从数量级来说，两个问题的时间复杂度相同，均为0（5）。

3.所有顶点对间最短路径问题 给定有向网G=（V, VR）,VR中每条弧＜Vi, Vj〉（v《V,Vj£V）都有非负的权。对网 中每对顶点V"和叩找岀从Vj到％的最短路径，这就是所有顶点对间最短路径问题 （All Pairs Shortest-Paths Problem） o 解决方法：可以采用把每个顶点作为源点调用一次单源最短路径算法予以解决。重复 执行ShortestPath_DIJ算法n次，其时间复杂度为O（n3）o

联系我们：