带权有向图的全源最短路径

全源最短路径

全源最短路径问题是指给定带权有向图，求任意两点\(u,v\)从\(u\)到\(v\)的最短路径”。可把该问题直接作为\(|V|\)个单源最短路径问题，使用Dijkstra算法(二叉堆)的代价为\(O(|V||E|lg|V|)\)，Bellman-Ford算法的代价为\(O(|V|^2|E|)\)，对于稠密图二者的代价可分别写成\(O(|V|^{3}lg|V|)\)与\(O(|V|^4)\)。本文将讨论专门用于解决全源最短路问题的算法，这些算法大多基于邻接矩阵讨论，且不允许存在任何负权环路的。下面给出相关定义：

1) 带权邻接矩阵：带权有向图\(G=(V,E)\)与其权重可被\(|V|\times |V|\)的矩阵\(W\)描述。其中\(W_{ij}\)表示图边\((i,j)\)的权重，并且当\(i=j\)时有\(W_{ij}=0\)，当图边\((i,j)\)不存在时有\(W_{ij}=\infty\)；

2) 最短路径值矩阵：用矩阵\(D\)描述最短路径值，其中\(D_{ij} = \delta(i,j)\)；

3) 前驱节点矩阵：当\(i=j\)或\(i\)不可达\(j\)时，\(\Pi_{ij}=None\)。否则\(\Pi_{ij}\)为\(i\)到\(j\)某个最短路中\(j\)的前驱；

基于矩阵乘法的算法

该算法的限制条件和用到的性质为：

a) 最优子结构：若\(i-…-k-j\)为最短路，则\(i-…-k\)为最短路，则\(D_{ij}=D_{ik}+W_{kj}\)；

b) 有环图：该算法不允许负权环路，故若\(i\)可达\(j\)则必然存在无环最短路，边数至多为\(|V|-1\)；

然后通过矩阵\(L^{(m)}\)给出递归解的结构：

1) 设矩阵\(L_{ij}^{(m)}\)为从\(i\)到\(j\)且至多含\(m\)条边的最短路值，则\(L^{(1)}=W\)；

2) 规定\(m=0\)时，若\(i=j\)，则\(L_{ij}^{(0)}=0\)，否则\(L_{ij}^{(0)}=\infty\)；

3) \(L_{ij}^{(m)} = min\{ L_{ij}^{(m-1)},~ min\{ ~ L_{ik}^{(m-1)} + W_{kj} ~|~ k\in V ~\} ~ \} = min\{ ~ L_{ik}^{(m-1)} + W_{kj} ~|~ k\in V ~\}\)；

4) 根据上述(b)可知\(D_{ij} = L_{ij}^{(|V|-1)} = L_{ij}^{(|V|)} = L_{ij}^{(|V|+1)} = … = L_{ij}^{(\infty)}\)；

类比\(A = L^{(m-1)} \times W\)的矩阵乘法，分析利用\(L^{(m-1)}\)与\(W\)求\(L^{(m)}\)的流程，发现把(i)的加法换为\(min(x,y)\)，乘法换为加法即得(ii)，该运算(计为\(\times\))是结合的，故\(L^{(m)}= L^{(m-1)} \times W = W^m\)。最短路值矩阵\(D\)可归纳为(iii)。

i) \(A_{ij} = \sum_{k\in V } (L_{ik}^{(m-1)} \cdot W_{kj}) = add(add(add( L_{i1}^{(m-1)} \cdot W_{1j} , L_{i2}^{(m-1)} \cdot W_{2j} ), L_{i3}^{(m-1)} \cdot W_{3j}),…  \)；

ii) \(L_{ij}^{(m)} = min\{ ~ L_{ik}^{(m-1)} + W_{kj} ~|~ k\in V \} = min(min( L_{i1}^{(m-1)} + W_{1j} , L_{i2}^{(m-1)} + W_{2j} ),… \)；

iii) 定义矩阵乘法\((AB)_{ij} = min\{ A_{ik} + B_{kj} |k\in V \}\)，给定\(n\times n\)的带权邻接矩阵\(W\)，则\(D=W^{n-1}\)；

考虑基于朴素的矩阵乘法与“重复平方”策略将上述分析转化为算法实现：

1) 对于两个\(n\times n\)方阵间的乘法，朴素矩阵乘法算法需要\(O(n^3)\)的代价，故对于\(n\times n\)方阵，计算\(A^{n-1}\)需要\(O(n^4)\)代价，故类比朴素算法计算上述“\(D=W^{n-1}\)”同样为\(O(n^4)=O(|V|^4)\)代价；

2) 可通过二分思路对矩阵幂次做“重复平方”优化，其流程为迭代的计算\((((W^2)^2)^2)^2…\)，第\(i\)次迭代求得\(W^{2^i}\)，每次迭代完若\(2^i \geq |V|-1 \)则该次迭代值即为解，无需严格要求\(2^i = |V|-1 \)是因为上述(3)给出的性质；

3) 由于每次迭代可看作求上次迭代结果的平方，故\(i\)次迭代需\(i\)次矩阵乘法，总乘法次数\(k\)有上界\(2^{k+1} \leq |V|-1 \)，即\(k = O(lg|V|)\)，“重复平方”算法的最坏代价为\(O(|V|^3lg|V|)\)；

最后讨论前驱节点矩阵，设\(\Pi_{ij}^{(m)}\)为从\(i\)到\(j\)且至多含\(m\)条边的某最短路中\(j\)的前驱，通过从左到右逐步“相乘”的方式求\(L_{ij}^{(m)}\)，即朴素乘法\((((W)W)W)…\)的计算方法，随这个流程记录取\(min\)时的具体顶点可求得\(\Pi_{ij}^{(m)}\)并整理得出\(\Pi_{ij}\)。但若用“重复平方”策略，计算\((L^{(k)})^2 \)对应\(\Pi^{(2k)}\)无明确意义，故上述算法未构造前驱节点矩阵\(\Pi\)。

Floyd-Warshall算法

该算法的限制条件和用到的性质为：

a) 顶点的表示：用邻接矩阵的行标(列标)表示顶点，比如对于\(n\times n\)邻接矩阵，其顶点集为\(\{1,2…,n\}\)；

b) 中间节点：简单路径\(p=1->2->…(n-1)->n\)的中间节点为集合\(\{2,…,{n-1}\}\)；

c) 最优子结构：设\(V=\{1,2,…,n\}\)。其有子集\(\{1,2,…,k\}\)，其中\(k<n\)。对于任意节点对\((i,j)\)，考虑其所有中间节点取自\(\{1,2,…,k\}\)的路径，\(p\)为其中最短路。若\(k\)不是\(p\)的中间节点，则\(p\)的中间节点都取自\(\{1,2,…,k-1\}\)，故中间节点取自\(\{1,2,…,k-1\}\)的最短路也是中间节点取自\(\{1,2,…,k\}\)的最短路。若\(k\)是\(p\)的中间节点，则可将\(p\)分解为两个子最短路\(p_1 = i -…- k\)与\(p_2 = k-…-j\)。那么\(p_1\)与\(p_2\)的中间节点都取自\(\{1,2,…,k-1\}\)；

d) 有环图：该算法同样不允许负权环路；

然后通过矩阵\(D^{(m)}\)给出最短路值矩阵\(D\)的递归结构：

1) 设\(D_{ij}^{(k)}\)为从\(i\)到\(j\)所有中间节点都取自\(\{1,2…k\}\)的最短路的权重；

2) \(D_{ij}^{(0)}\)表示无中间节点的情况，所以规定\(D_{ij}^{(0)}=W_{ij}\)；

3) \(k\)的其他情况根据最优子结构，\(D_{ij}^{(k)} = min\{~ D_{ij}^{(k-1)} , D_{ik}^{(k-1)} + D_{kj}^{(k-1)}   ~\}\)；

4) 设\(n\)为图顶点数，则最终\(D_{ij} = \delta(i,j) = D_{ij}^{(n)}\)；

然后通过矩阵\(\Pi^{(m)}\)给出前驱节点矩阵\(\Pi\)的递归结构：

1) 设\(\Pi^{(k)}\)为从\(i\)到\(j\)的某条所有中间节点都来自\(\{1,2…k\}\)的最短路中\(j\)的前驱；

2) \(\Pi_{ij}^{(0)}\)表示无中间节点的情况，当\(i=j\)或\(W_{ij}=\infty\)时\(\Pi_{ij}^{(0)}=None\)，否则\(W_{ij}=j\)；

3) \(k\)的其他情况，若\(D_{ij}^{(k-1)} \leq D_{ik}^{(k-1)} + D_{kj}^{(k-1)} \)有\(\Pi_{ij}^{(k)} = \Pi_{ij}^{(k-1)} \)；

4) \(k\)的其他情况，若\(D_{ij}^{(k-1)} > D_{ik}^{(k-1)} + D_{kj}^{(k-1)} \)有\(\Pi_{ij}^{(k)} = \Pi_{kj}^{(k-1)} \)；

最后通过自底向上的迭代次序实现该算法，可以发现该算法属于DP算法，其代价为\(O(|V|^3)\)；

Johnson算法

该算法的限制条件和用到的性质为：

a) 有环图：该算法同样不允许负权环路，但其可以检测到负权环路；

b) “重新赋予权重”：若图中无负权边，则对每个节点执行Dijkstra算法即可。若图中存在负权边，但无负权环路，则需要为每个边计算一组新的非负权重值，然后执行Dijkstra算法即可。其中新权重函数\(w’\)必须满足如下性质：

b.i) 原权重\(w\)下的任意节点对间的任意最短路\(p\)，新权重\(w’\)必须使\(p\)仍为最短路；

b.ii) 任意边的新权重\(w’\)是非负值；

c) “重新赋予权重”引理：\(w'(u,v)=w(u,v)+h(u)-h(v)\)，\(h(x)\)为任意函数。设\(p\)为\(u\)到\(v\)的任意路径。

c.i) \(p\)为\(w\)下的最短路径 \(<=> \) \(p\)为\(w’\)下的最短路径；

证明：对\(p\)求权重和，错位相减得\(\sum_{x \in p}w'(x)=(\sum_{x \in p}w(x))+h(u)-h(v)=(\sum_{x \in p}w(x))+C\)。故从\(u\)到\(v\)的任意路径的总权重，其与原权重的差是固定的常数，原权重最短路必为新权重最短路。

c.ii) \(G\)在\(w\)下无负权环路 \(<=> \) \(G\)在\(w’\)下无负权环路；

证明：若\(p\)为环路，\(\sum_{x \in p}w'(x)=(\sum_{x \in p}w(x))+h(u)-h(u)=\sum_{x \in p}w(x)\)。

给出算法的流程如下，其中步骤(1)(2)的方法在之前差分约束的文章中讨论过。

1) 在\(G\)中加入新顶点\(s\)，并初始化\(s\)有到达所有其他顶点的0权重出边，把更改后的图计为\(G’\)；

2) 在\(G’\)的\(s\)运行Bellman-Ford算法，求得每个\(\delta(s,v)\)并判断原图\(G\)有无负权环路(差分约束文章里讨论过)；

3) 设\(h(v)=\delta(s,v)< \infty\)，利用三角不等式有\(w'(u,v)=w(u,v)+h(u)-h(v) \geq 0\)；

4) 然后以\(w’\)为权重，对\(G\)的每个顶点执行Dijkstra算法；

5) 原权重与新权重的最短路值满足\(\delta(s,v) + h(s) – h(v) = \delta'(s,v)\)（利用和证明引理相同的方法可证）；