20220101-《算法导论》第25章-每对顶点间的最短距离
学习笔记：《算法导论》第25章-每对顶点间的最短距离
0. 提出背景
- 问题：对一张公路图，需要制表说明每对城市间的距离。
- 概述：
- 基于矩阵乘法的动态规划算法，求解每对顶点间的最短路径问题【重复平方】；
- 动态规划算法Floyd-Warshall算法；
- 有向图传递闭包问题【与每对顶点间最短路径有关系】；
- Johnson算法【采用图的邻接表表示法】；
1. 最短路径与矩阵乘法
基于动态规划算法，用来解决有向图上每对顶点间的最短路问题；
动态规划的每一次主循环都将引发一个与矩阵乘法十分相似的操作，因此算法看上去很像是重复的矩阵乘法；
设计思想：通过把最短路径延长，最终计算出最短路径权值；
设计步骤：
最短路径的结构
$\delta(i, j)=\delta(i, k)+w_{k j}$；
每对顶点间最短路径问题的一个递归解：
- $n$：顶点数量；
$l_{i j}^{(m)}$：表示从顶点i到顶点j的至多包含m条边的任何路径的权值最小值；
当m大于等于1时，有：
$l_{i j}^{(m)}=\min \left(l_{i j}^{(m-1)}, \min _{1 \leq k \leqslant n}\left\{l_{i k}^{(m-1)}+w_{k j}\right\}\right)=\min _{1 \leq k \leqslant n}\left\{l_{i k}^{(m-1)}+w_{k j}\right\}$；
其中第二个等式成立，是因为$w_{jj}=0$；
$\delta(i, j)$：表示实际最短路径权值；
当$\delta(i, j)<\infty$：存在一条从i到j的最短路径，且为简单路径，从而最多包含n-1条边；
由于从顶点i到顶点j的对于n-1条边的路径权值不可能小于从i到j的最短路径的权值，因此实际的最短路径权值：$\delta(i, j)=l_{i j}^{(n-1)}=l_{i j}^{(n)}=l_{i j}^{(n+1)}=\cdots$；
自底向上计算最短路径的权值：
- 输入：$W=\left(w_{i j}\right)$
- 输出：$L^{(1)}, L^{(2)}, \cdots, L^{(n-1)}$，且$L^{(m)}=\left(l_{i j}^{(m)}\right)$；
- 用$L$表示$L^{(m-1)}$；
- 用$L^{\prime}$表示$L^{(m)}$；
和矩阵乘法的联系：
矩阵乘法：$c_{i j}=\sum_{k=1}^{n} a_{i k} \cdot b_{k j}$
替换：
2. Floyd-Warshall算法
提出：允许存在权值为负的边，但是不存在权值为负的回路；
中间节点：简单路径$p={v_1,v_2,…v_l}$上的中间顶点是除了$v_1$和$v_l$以外上的任何一个顶点，即任何属于集合${v_2,v_3,…,v_{l-1}}$的顶点；
设计思路：利用了路径p与从i到j之间的最短路径之间的联系；
设计步骤：
最短路径的结构
如果k不是路径p的中间顶点：p的所有中间节点都在$\{1,2,…,k-1\}$中，因此从顶点i到顶点j且满足所有中间顶点皆属于$\{1,2,…,k-1\}$的一条最短路径，同样也是从i到j且满足所有中间顶点皆属于集合$\{1,2,…,k\}$的一条最短路径；
如果k是路径p的中间顶点：因为k不是路径p1上的一个中间顶点，所以p1是从i到k的一条最短路径，且其所有中间顶点均属于集合$\{1,2,…,k-1\}$；类似地，p2是从k到j的一条最短路径，且其所有中间顶点均属于集合$\{1,2,…,k-1\}$；
3. 稀疏图上的Johnson算法
- 提出：运用了重赋权技术；
- 执行方式：如果所有边权w非负，则把每对顶点依次作为源点来执行Dijkstra算法，就可以找出每对顶点间的最短路径，可以使用斐波那契最小优先队列进行优化；如果G含有负权边但是不含有负权的回路，就只计算一个心的负权边的集合。
- 重赋权值不会改变最短路径。