软件设计师考试考点分析与真题详解：最短路径

带权图的最短路径问题即求两个顶点间长度最短的路径。其中，路径长度不是指路径上边数的总和，而是指路径上各边权值的总和。路径长度的具体含义取决于边上权值所代表的意义。

1.单源最短路径

已知有向带权图(简称有向网)G=(V,E)，找出从某个源点s∈V到V中其余各顶点的最短路径，称为单源最短路径。

目前，求单源最短路径主要使用迪杰斯特拉(Dijkstra)提出的一种按路径长度递增序产生各顶点最短路径的算法。若按长度递增的次序生成从源点s到其他顶点的最短路径，则当前正在生成的最短路径上除终点以外，其余顶点的最短路径均已生成(将源点的最短路径看成是已生成的源点到其自身的长度为0的路径)。

迪杰斯特拉算法的基本思想是：设S为最短距离已确定的顶点集(看成红点集)，V-S是最短距离尚未确定的顶点集(看成蓝点集)。

(1)初始化：初始化时，只有源点s的最短距离是已知的(SD(s)=0)，故红点集S={s},蓝点集为空。

(2)重复以下工作，按路径长度递增的次序产生各顶点的最短路径：在当前蓝点集中选择一个最短距离最小的蓝点来扩充红点集，以保证算法按路径长度递增的次序产生各顶点的最短路径。当蓝点集中仅剩下最短距离为∞的蓝点，或者所有的蓝点已扩充到红点集时，s到所有顶点的最短路径就求出来了。

需要注意的是：

(1)若从源点到蓝点的路径不存在，则可假设该蓝点的最短路径是一条长度为无穷大的虚拟路径。

(2)从源点s到终点v的最短路径简称为v的最短路径;从s到v的最短路径长度简称为v的最短距离，并记为SD(v)。

根据按长度递增的次序产生最短路径的思想，当前最短距离最小的蓝点k的最短路径是：

源点，红点1.红点2.……，红点n,蓝点k

距离为：

源点到红点n最短距离 +

为求解方便，可设置一个向量D[0…n–1],对于每个蓝点v∈V–S,用D[v]记录从源点s到达v且除v外中间不经过任何蓝点(若有中间点，则必为红点)的"最短"路径长度(简称估计距离)。若k是蓝点集中估计距离最小的顶点，则k的估计距离就是最短距离，即若D[k]=min{D[i] i∈V–S},则D[k]=SD(k)。

初始时，每个蓝点v的D[c]值应为权w

将k扩充到红点后，剩余蓝点集的估计距离可能由于增加了新红点k而减小，此时必须调整相应蓝点的估计距离。对于任意的蓝点j,若k由蓝变红后使D[j]变小，则必定是由于存在一条从s到j且包含新红点k的更短路径P=

2.每一对顶点之间的最短路径

对图中每对顶点u和v,找出u到v的最短路径问题。这一问题可用每个顶点作为源点调用一次单源最短路径问题的迪杰斯特拉算法予以解决。

但更常用的是弗洛伊德(Folyd)提出的求每一对顶点之间的最短路径的算法。设G=(V,E)是有n个顶点的有向图，顶点集合V={0.1.…，n–1}.图用邻接矩阵M表示。Floyd算法的基本思想是递推地产生一个矩阵序列C0.C1.C2.…，Cn,其中C0是已知的带权邻接矩阵a,Ck(i,j)(0≤i,j<n)表示从顶点i到顶点j的中间顶点序号不大于k的最短路径长度。如果i到j的路径没有中间顶点，则对于0≤k

设在第k次递推之前已求得Ck-1(i,j)(0≤i,j<n)，为求ck(i,j)需考虑以下两种情况。< p="">

(1)如果从顶点i到顶点j的最短路径不经过顶点k,则由Ck(i,j)定义知，从i到j中间的顶点序号不大于k的最短路径长度还是Ck-1(i,j)即Ck(i,j)=Ck-1(i,j)。

(2)如果从顶点i到顶点j的最短路径要经过顶点k,则这样的一条路径是由 i到k和由k到j的两条路径所组成的。由于Ck-1(i,k)和Ck-1(k,j)分别表示i到k和从k到j的中间顶点序号不大于k-1的最短路径长度，若Ck-1（i,k）+Ck-1（k,j）<Ck-1（i,j），Ck-1（i,k）+Ck-1（k,j）必定是i到j的中间顶点序号不大于是k的最短路径的长度，则Ck（i,j）=Ck-1（i,k）+Ck-1（k,j）。