Mengzelev's Blog

算法导论学习笔记-所有结点对的最短路径问题

Word count: 551 / Reading time: 2 min
2018/11/07 Share

矩阵乘法

最优子结构

$l_{ij}^(m)}$:从结点$i$到结点$j$的至多包含$m$条边的任意路径中的最小权重。
$$
l_{ij}^{(m)} = \min\limits_{1\lek\le n}{l_{ik}^{(m1)}+w_{kj}}
$$

自底向上计算最短路径权重

三重循环,时间复杂度为$\Theta(n^3)$

形式上与矩阵乘法的计算非常类似

计算$L^{(n-1)}=W^{n-1}$


这个算法本质上就是对$n$个点每个跑了一遍Bellman-Ford

改进运行时间

重复平方技术
二分计算矩阵的幂

优化后时间复杂度为$\Theta(n^3\lgn n)$

Floyd-Warshall算法

枚举最短路径上的中间结点来进行递归的计算

  • 不允许有负权重环
  • 但是可以做到在有负权重环的情况下报告(看对角元是否有负数)

$d_{ij}^{(k)}$:从$i$到$j$经过的中间结点为${1,…k}$的子集的最短路径长度

伪代码

时间复杂度

$\Theta(n^3)$

空间复杂度

看似需要$\Theta(n^3)$,但是作业题中证明了只需要一个矩阵来存储,为$\Theta(n^2)$

构建最短路径

采用动态规划的思想,递推式如下

用于稀疏图的Johnson算法

用一种神奇的方式对图中每条边的权重进行重新赋值,使新的图满足

  • 所有权重都为非负值
  • 新图中的最短路径就是旧图中的最短路径

伪代码

先增加一个新结点$s$,该点到原先各结点都有边相连,权重为0
对新图进行一次Bellman-Ford算法,寻找是否有负权重环路
没有负权重环,就用神奇的长得像顶点的势能函数一样的函数给每条边重新赋值
$$ \hat{w}(u,v)=w(u,v)+h(u)-h(v)$$
$$ h(u)=\delta(s,u)$$
然后对每个点进行Dijkstra
最后记得将最短路径的权重恢复,并存入矩阵$D$中返回

时间复杂度

二叉最小优先队列实现Dijkstra:$O(VE\lg V)$
斐波那契堆实现:$O(V^2\lgV+VE)$
在稀疏图的情况下,表现比Floyd-Warshall好

CATALOG
  1. 1. 矩阵乘法
    1. 1.1. 最优子结构
    2. 1.2. 自底向上计算最短路径权重
    3. 1.3. 改进运行时间
  2. 2. Floyd-Warshall算法
    1. 2.1. 伪代码
    2. 2.2. 时间复杂度
    3. 2.3. 空间复杂度
    4. 2.4. 构建最短路径
  3. 3. 用于稀疏图的Johnson算法
    1. 3.1. 伪代码
    2. 3.2. 时间复杂度