chap25 所有结点对的最短路径问题

矩阵乘法 Floyd-Warshall算法 Johnson算法 算法导论

内容

概览

1. 前驱结点矩阵$\Pi = (\pi_{ij})$,，其中$\pi_{ij}$给出从结点i到结点j的耨条最短路径上的结点j的前驱结点
2. 前驱子图$G_{\pi ,i} = (V_{\pi ,i},E_{\pi ,i})$,其中$V_{\pi ,i}= \left \{ j \in V:\pi _{ij} \neq NIL \right \} \cup \left \{ i \right \}$,即i和i能够到达的结点集$; E_{\pi ,i}= \left \{ (\pi _{ij},j) :j \in V_{\pi ,i}-\left \{ i \right \} \right \}$,即点集中该点和他的前驱组成的边集
3. print-path(Pi,i,j)

.

if i == j
    print i
else if pi[ij] = nil
    print no path
else
    print-path(Pi,i,pi[ij])
    print j

最短路径和矩阵乘法

1. 最短路径的结构，基于引理24.1，最短路径的子路径也是最短路径
2. 迭代关系：$l_{ij}^{m}=min(l_{ij}^{(m-1)},min_{1\leqslant k \leqslant n} \left \{ l_{ik}^{(m-1)} + w_{k,j}\right \})$$=min_{1\leqslant k \leqslant n} \left \{ l_{ik}^{(m-1)} + w_{k,j}\right \}$
3. 其中$l_{ij}^{m}$表示从结点i到结点j的至多包含m多条的任意路径中的最小权重，因而当m=n-1时，$L^{n-1}= (l_{ij}^{n-1})$就是原问题的解
4. 根据迭代关系的形式，基于动态规划的思想，并使用重复平方技术来计算

extended-shortest-paths(L,W)

n = L.rows
let L' to be a new n by n matrix
for i = 1 to n
    for j = 1 to n
        l'[ij] = 00
        for k = 1 to n
            l'[ij] = min(l'[ij], l[ik]+w[kj])
return L'

使用重复平方技术——$\Theta(n^3 \lg n)$
faster-all-pathsirs-shortest-paths(W)

n = W.rows
L_1 = W
m = 1
while m < n-1
    let L_2m = extended-shortest-paths(L_m,L_m)
    m = 2m
return L_m

Floyd-Warshall算法

1. 条件：不存在权重为负值的环路
2. 仍然是动态规划的思想，但是用另一种动态规划公式来求解，或者说对子问题的空间划分不同。上面的算法，它是以最短路径包含的边数的最大值作为问题空间的规模；而这里，将最短路径包含的中间节点所属的集合的作为子问题的问题空间，集合的大小便是问题空间的规模
3. 这里的集合是有限制的，即大集合包含小集合。具体做法就是对所有结点编个号，然后大规模的集合ei比是小规模的集合并上那些大编号的结点

4. 思考下，为什么两种动态规划的时间相差一个量级（不考虑重复平方技术）呢？

   • 个人认为，原因还是在于动态规划降低复杂度的本质在于减少重复运算。因而后者定是对于重复计算的利用率高，直观上来看，后者的做法与chap15中LCS的操作流程基本一致
   • 前者对于边的条数的考虑，并没有使得小规模的问题的结果得到利用，因为原问题的解和边的条数并不是直接相关的，当然得到小问题的边数和得到小问题的中间结点个数是等价的，二者都很难直接利用，但是后者在得到中间结点个数的同时，还因为子问题空间即中间结点集的包含关系，使得后者在获得中间结点个数的同时还得到了更多的信息，而这种信息，使得子问题的解得到更加充分的利用
   • 简单说就是，前者所分成的子问题的解和原问题的求解方向相关性较差，而后者相关性高（这里求解方向意思是：大问题求解5的阶乘，小问题相关就是在求3的阶乘，不相关就是求3的平方，相关性差就是求$2\times C_{3}^2$）
   • 补充：概括说就是，前者的子问题空间并没有相关性，边数不同的边集是不确定的，只知道这个集合里有几条边，但是包含哪些边并不清楚；而后者子问题集之间有依赖关系，根据这种关系，问题空间被不断细化，这与chap15中典型动态规划的算法的做法是一致的
   • 因而结论就是在利用动态规划思想时，要尽量以和原问题的解相关的量构建关系式，如这里的中间结点集合，；在划分子问题时，应该尽量让子问题空间之间具有明显的依赖关系，这样在问题回溯时能方便地得到大问题的解

5. 关系式：$d_{ij}^{k} = \begin{cases} & w_{ij} \text{ if } k=0\\ & min (d_{ij}^{k-1},d_{ik}^{k-1}+d_{kj}^{k-1}) \text{ if } k \geqslant 1 \end{cases}$

6. 一些细节，注意k的上限是n，不是n-1，如果是n-1的话，那么$d_{i,j\neq n}$将因无法考虑包含中间结点n的情况而可能出错

自底向上
floyd-warshall(W)

n = W.rows
D_0 = W
for k = 1 to n
    let D_k be a new matrix
    for i = 1 to n
        for j = 1 to n
            5中关系式
return D_n

有向图的传递闭包

1. 有向图$G$的传递闭包为$G^* = (V,E^*)$,其中$E^*=\left \{ (i,j)：G中包含一条从i到j的路径\right \}$
2. 方法1，使用Floyd-Warshall算法，将边的权重赋为1，去寻找那些d为有限值的（i，j）
3. 方法2： 在实际场景中能够比1节省时间和空间，使用逻辑或操作和逻辑与操作来代替FW算法中min和+
4. 关系式：
   $t_{ij}^{0} = \begin{cases} & 0 \text{ 若 } i \neq j 且 (i,j) \notin E\\ & 1 \text{ 若 } i = j 或 (i,j) \in E \end{cases}$
   对于$k \geqslant 1$
   $t_{ij}^{k}=t_{ij}^{k-1}\vee (t_{ik}^{k-1}+t_{kj}^{k-1})$

transitive-closure(G)

n = |G.V|
let T_0 be a new matrix and initialize it obey formula dexcribed as 4
for k = 1 to n 
    let T_k be a new matrix
    for i = 1 to n
        for j = 1 to n
            关系式4
return T_n

稀疏图——Johnson算法

1. 条件：不存在权重为负值的环路
2. 基于Dijksrtra算法，使用菲波那切最小有限队列则复杂度为$O(V^2\lg V+VE)$,使用二叉最小堆的复杂度为$O(VE\lg V )$
3. 为了满足Dijkstra算法对于边权重为非负数的要求，当存在负权重时，需要重新赋予权重以满足要求
4. 基于引理25.1，做法是在原图上加上一个结点s，并加上s和所有原图中结点相连的权重为0的有向边。算法第一步及时使用Bellman-Ford算法以s为源结点求出所有的$h(u) =\delta(s,u)$,h即为引理中的“任意函数”
5. 伪代码：

Johnson(G,w)

compute G'
if bellman-ford(G',s) == false
    print "the input graph contains a negative-weight cycle"
else
    for each vertex v in G.E
        set h(v) to the value computed by the bellman-ford algorithm
    for each edge(u,v) in G'.E
        w'(u,v) = w(u,v) + h(u) - h(v)
    let D be a new n by n matrix
    for each vertex v in G.E
        run dijkstra(G,w',u) to compute delta(u,v) for all v in G.V
        for each vertex in G.V
            d[uv] = delta(u,v) + h(v) - h(u)
return D

习题

to be continued

代码实现