最短路径概述

最短路径
在最短路径问题中，我们给定一个带权重的有向图G=(V,E)，和权重函数w，E→R,该权重函数将每条边映射到实数值的权重上。图中一条路径p=(v0,v1…,vk)的权重w(p)是构成该路径的所有边的权重之和。
定义从结点u到结点v的最短路径权重δ(u,v)如下
δ(u,v)=min(w(p)，p是u到v的任意一条路径。
否则=∞
最短路径的几个变体
单目的地最短路径问题：找到从每个结点v到给定目的地结点t的最路径问题。
单结点对的最短路径问题：找到从给定结点u到给定结点v的最短路径问题。
所有结点对最短路径问题：对于每对结点u和v，找到从结点u到结点v的最短路径。
最短路径的最优子结构
两个结点之间的一条最短路径包含着其它的最短路径。
引理(最短路径的子路径也是最短路径)：给定一个带权有向图G=(V,E)。设p=(v0,v1,…vk)为结点v0到vk的一条最短路径，并且对于任意i和j，0≤i≤j≤k，设pij=(vi,vi+1,…,vj)为路径p从结点vi到结点vj的子路径，那么pij是从结点vi到结点vj的一条最短路径。
负权重的边
某些单源最短路径问题可能包括权重为负值的边。但如果G=(V,E)不包括从源点s可以到达的权值为负值的环路，则对于所有结点v∈V，最短路径权重δ(u,v)都有精确定义，即使取值是负数。如果图包含从s可以到达的权重为负值的环路，则最短路径权重无定义。从s到该环路上的任意结点的路径都不可能是最短路径，因为我们只要沿着你任何“最短”路径再遍历一次权重为负值的环路，则总是可以找到一条权重更小的路径。如果从结点s到结点v的某条路径上存在权重为负值的环路，我们定义δ(u,v)=-∞
环路
一条最短路径可以包含环路吗？正如我们已看到，最短路径不能包含权重为负值的环路，而事实上最短路径与不能包含权重为正的环路，因为只要将环路从路径上删除就可以得到一条源结点到终结点与原来路径相同的一条权重更小的路径。
因此，不失一般性，我们可以假定在找到的最短路径中没有环路，即它们都是简单路径，由于图G=(V,E)中任意无环路最多包含|V|不同我结点，它也最多包含|V|-1条边。因此我们可以将注意力集中到至多包含|V|-1条边的最短路径中。
最短路径的表示
在通常情况下，我们不但希望计算出最短路径权重，还希望计算出最短路径上的结点。给定图G=(V,E)，对于每个结点v，我们维护一个前驱结点vΠ。该前驱结点可以是另一个结点或NIL。最短路径算法将对每个结点的Π属性进行设置，这样，将可以从结点v开始的前驱结点链反转过来，就是从s到结点v的一条最短路径。
松驰操作
对于每个结点来说，我们维持一个属性v.d，用来记录从源点s到结点v的最短路径权重的上界。我们称v.d为s到v的最短路径估计。
我们可以使用下面运行时间为θ(V)的算法对最短路径估计和前驱进行初始化

Initialize Singl_source(G,s)
for each vertex v∈G.V
    v.d=∞
    v.п=NIL
s.d=0

对一条边(u,v)的松驰过程为，首先测试一下是否可以对从s到v的最短路径进行改善。测试的方法是，将从s到u之间的最短路径距离加上结点u到v之间的边权，并与当前的s到v的最短路径估计进行比较，如果前者小，则对v.d和v.п进行更新。松驰操作可以降低最短路径的估计值v.d并更新v的前驱属性v.п。

松驰操作

RELAX(u,v,w)
   if v.d>u.d+w(u,v)
      v.d=u.d+w(u,v)
      v.п=u

不同的算法之间的不同之处是对每条边进行松驰的次数与松驰边的次序有所不同。

最短路径和松驰操作的性质
三角不等式性质
对于任何边(u,v)∈E，我们有δ(s,v)≤δ(s,u)+w(u,v)。
上界性质
对于所有的结点v∈V，我们总是有v.d≥δ(s,v)，一旦v.d的取值达到δ(s,v)，其值将不再发生改变。
非路径性质
如果从结点s到结点v之间不存在路径，则总是v.d= δ(s,v)=∞
收敛性质
对于某些结点u,v∈V，如果s~u→v是图G中的一条最短路径，并且在对边(u,v)进行松驰前的任意时间有u.d=δ(s,u)，则在之后的所有时间有v.d=δ(s,v)。
路径松驰性质
如果p=(v0,v1,…,vk)是从源点s=v0到vk的一条最短路径，并且我们对p中的边所进行的松驰次序为(v0,v1),(v1,v2)…(vk-1,vk)，则vk.d=δ(s,vk)。该性质的成立与任何其他的松驰操作无关，即使这些松驰操作是与对p上的边所进行的松驰操作穿插进行的。
前驱子图性质
对于所有结点v∈V，一旦v.d=δ(s,v)，则前驱子图是一棵根结点为s的最短路径 树。
最短路径算法
迪杰斯特拉(Dijkdtra)
Bellman-Ford最短路径算法
SPFA算法
Floyd - Warshall（弗洛伊德算法）
Johnson 全源最短路径算法
最短路径算法不同方法的比较