最短路径（SP）问题
1st revision - 2024-12-28
前言
介绍的最短路径的算法以有向图（强连通）为基础，但也适用于无向图的情况，只是在涉及负环时情况略有不同1。
遵循依赖关系，将依次介绍：
- Floyd 算法 （全源）
- Bellman-Ford 算法 （单源）
- Bellman-Ford 算法的著名改进： SPFA 算法 （单源）
- Dijkstra 算法 （单源）
- Johnson 算法 （全源）
Floyd 算法
/flɔid/
算法思想
这个算法当初是作为一个动态编程的范例提出，全源地计算图上最短路径问题。
假如对图上所有点编号 $1…n$ ，那么图上任何一条最短路径最多经过 $n$ 个点。一开始，我们只知道直接相连的两点之间的路径权重，但可以通过检查是否有 $w[x][1] + w[1][y] < w[x][y]$ 得到最多经过点 $1$ 的两点间的最小路径。在此基础上如果在检查一遍经过点 $2$ 的两点间最短路径，就可以得到最多经过 $\lbrace 1,2 \rbrace$ 的两点间最短路径，以此类推，当检查过 $n$ 轮，就得到了最多经过 $\lbrace 1,2, …, n \rbrace$ 的最短距离，也就是整个图上的最短距离。
伪代码
对于图 $G=(V, E)$
\[\begin{array}{ll} \texttt{let}\ w[x][y]\ \text{as shortest path's weight sum from}\ x\ \text{to}\ y\\ \texttt{let}\ w_{xy}\ \text{as edge weight from}\ x\ \text{to}\ y\\ \\ \texttt{for}\ x \gets \{1,2,..,n\}\\ \qquad\texttt{for}\ y \gets \{1,2,...,n\}\\ \qquad\qquad \texttt{if}\ x=y\\ \qquad\qquad\qquad w[x][y] \gets 0\\ \qquad\qquad\ \texttt{elif}\ (x, y)\notin |E| \\ \qquad\qquad\qquad w[x][y] \gets \infty \\ \qquad\qquad\ \texttt{else}\\ \qquad\qquad\qquad w[x][y] \gets w_{xy} \\ \texttt{for}\ k \gets \{1,2,..,n\}\\ \qquad\texttt{for}\ x \gets \{1,2,...,n\}\\ \qquad\qquad\texttt{for}\ y \gets \{1,2,...,n\}\\ \qquad\qquad\qquad w[x][y] = \texttt{min}(w[x][k],\ w[k][y]) \end{array}\]路径构造
如果单独地为每一对儿点存储独立路径，那么空间复杂度是 $O(n^3)$ ，有时候这可能不太妙，可以使用 $\text{next}$ 数组，存储一条路径的第一步的端点，用 $O(n)$ 的时间复杂度换取 $O(n^2)$ 的空间复杂度。
对于一条路径 $x_1 \rightarrow x_2 \rightarrow x_3\ …\rightarrow x_n$：
\[\begin{array}{ll} \text{next}[x_1][x_n] &= x_2\\ \text{next}[x_2][x_n] &= x_3\\ \text{next}[x_{n-1}][x_n] &= x_n \end{array}\]每次更新权重的时候，更新 $\text{next}$ 数组：
\[\text{next}[x][y] = \text{next}[x][k]\]查询 $x \rightarrow y$ 最小路径时，展开 $\text{next}$ 数组（输出一个 $(x)..y$ 的路径，下同）：
\[\begin{array}{l} \texttt{let}\ \text{sequential set P as path output}.\\ \\ p\ \gets x\\ P \gets \varnothing\\ \\ \texttt{loop if}\ \ p \neq y\\ \qquad p \gets \text{next}[p][y]\\ \qquad P \gets p \\ \end{array}\]负环问题
负环是指一条环状路径，其权重和为负值。显然负环的存在会使最短路径问题根本上不可解，因为任何一条路径都可以通过负环使得其权重和无限地减低下去。
对于有向图而言，显然 Floyd 可以处理不存在负环的负边的情况。但对于无向图，负边实质上是不可能的。因为无向图必须转为有向图来应用算法，而无向图的每条负边都意味着有向图的一个两条边构成的负环，或者说至少需要特别检查和处理两点构成的负环。
所以我们下面讨论的有向图负边权情况下探测负环的问题 。
方法是检查对角线上元素，也就是 $w[i][i], i \in \vert V\vert$ ，是否小于 $0$ ，如果是，意味着存在 $i\rightarrow i$ 的负环。
负环探测
\[\begin{array}{l} \texttt{let}\ \text{sequential set C as cycle output}\\ \texttt{let}\ \text{c as the known cycle vertex}\\ \\ C \gets \lbrace c \rbrace \\ p \gets \text{next}[c][c] \\ \\ \texttt{loop if}\ p \neq c\\ \qquad C \gets p\\ \qquad c \gets \text{next}[p][c] \end{array}\]实现
pub struct SPFloyd<'a> {
g: &'a Graph,
/// shortest path weight
spw: M1<(usize, usize), isize>,
//// shortest path paths
next: M2<usize, usize, usize>,
}
impl<'a> SPFloyd<'a> {
pub fn new(g: &'a Graph) -> Result<Self, Vec<usize>> {
let (spw, next) = sp_floyd(g)?;
Ok(Self { g, spw, next })
}
/// (total_weight, (src), .. , k1, k2, .. dst)
pub fn query(&self, src: usize, dst: usize) -> (isize, Vec<usize>) {
(
get!(self.spw => (src, dst)),
next_to_path((src, dst), &self.next),
)
}
}
fn sp_floyd(
g: &Graph,
) -> Result<(M1<(usize, usize), isize>, M2<usize, usize, usize>), Vec<usize>> {
let mut vertexs: Vec<usize> = g.vertexs().collect();
vertexs.sort_unstable();
let n = vertexs.len();
let mut spw = M1::<(usize, usize), isize>::new();
let mut next = M2::<usize, usize, usize>::new();
/* init sp */
for x in 0..n {
for y in 0..n {
let x = vertexs[x];
let y = vertexs[y];
if let Some(w) = getopt!(g.w => (x, y)) {
set!(spw => (x, y) => w);
set!(next => (x, y) => y);
} else if x == y {
set!(spw => (x, y) => 0);
}
}
}
for k in 0..n {
for x in 0..n {
for y in 0..n {
let x = vertexs[x];
let y = vertexs[y];
let k = vertexs[k];
if let Some(w_xk) = getopt!(spw => (x, k)) &&
let Some(w_ky) = getopt!(spw => (k, y))
{
if getopt!(spw => (x, y)).is_none() ||
w_xk + w_ky < get!(spw => (x, y))
{
set!(spw => (x, y) => w_xk + w_ky);
set!(next => (x, y) => get!(next => (x, k)));
if x == y && w_xk + w_ky < 0 {
let mut cycle = vec![x];
let mut c = get!(next => (x, y));
while c != y {
cycle.push(c);
c = get!(next => (c, y));
}
return Err(cycle);
}
}
}
}
}
}
Ok((spw, next))
}
时间复杂度
显然时间复杂度为 $O(n^3)$
Bellman-Ford 算法
/ˈbelmən/-/fɔrd/
算法思想
对比前面的 Floyd 算法考虑最短路径经过的点，Bellman-Ford 则考虑最短路径经过的边。
考虑对于 $n$ 个点的图，每一条最短路径最多包含 $n-1$ 条边（否则必然存在负环），从一条边的情况开始，遍历每条边，检查每个点到源点的最短距离是否可以被这条边更新，最后得到了最多包含一条边的最短路径；第二轮迭代，解决了最多包含两条边的情况；直到第 $n-1$ 轮，所有最短路径都必然已经得到。如果此时检查还有可以被边更新的最短路径，就必然存在负环。
伪代码
对于图 $G=(V, E)$ ，源点 $s$ ：
\[\begin{array}{l} \texttt{let}\ \text{dis}[x]\ \text{as shortest path's distance from}\ s\ \text{to}\ x \\ \texttt{let}\ w_{xy}\ \text{as edge weight from}\ x\ \text{to}\ y\\ \\ \texttt{for}\ x \gets |V|\\ \qquad \texttt{if}\ x = s\\ \qquad\qquad \text{dis}[x] \gets 0\\ \qquad \texttt{elif}\ (s,x) \in |E|\\ \qquad\qquad \text{dis}[x]=w_{sx} \\ \qquad \texttt{else}\\ \qquad\qquad \text{dis}[x] = \infty\\ \\ \texttt{iterate}\ \text{|V|-1 times} \\ \qquad\texttt{for}\ (x, y) \gets |E|\\ \qquad\qquad \text{dis}[y] = \texttt{min}(\text{dis}[y],\ \text{dis}[x] + w_{xy}) \end{array}\]路径构造
由于是加边的构造过程，路径构造采用了反向的 $\text{pre}$ 数组。
对于一条路径 $(s) \rightarrow x_1 \rightarrow x_2 \rightarrow x_3\ …\rightarrow x_n$：
\[\begin{array}{ll} \text{pre}[x_n] &= x_{n-1}\\ \text{pre}[x_{n-1}] &= x_{n-2}\\ \text{pre}[x_{2}] &= x_1 \end{array}\]每次更新权重的时候，更新 $pre$ 数组：
\[\text{pre}[y] = \text{pre}[x]\]查询 $x \rightarrow y$ 最小路径时，展开 pre 数组：
\[\begin{array}{l} \texttt{let}\ \text{sequential set P as path output.}\\ \\ P \gets \varnothing \\ p \gets y \\ \\ \texttt{loop if}\ p \neq x\\ \qquad P \gets p\\ \qquad p \gets \text{pre}[p]\\ \\ \texttt{reverse}\ P\\ \end{array}\]负环问题
负环问题前面已经讲过，前面的 Floyd 算法因为是“加点”的诱导推理过程，因此处理负权边的无向图即使没有负环，也会将负权边视为两点构成的负环导致结果出错，而 Bellman-Ford 算法是“加边”的诱导推理过程， 就可以避免这种问题。
负环探测
当 $n-1$ 轮迭代后如果仍然有可以被更新的点，那么必然存在负环，而该点要么在负环上，要么在负环的下游。
这样以该点开始，用 $\text{pre}$ 数组向后找 $n$ 次，可以确保点一定在负环上，然后就可以构造负环路径。
\[\begin{array}{l} \texttt{let}\ \text{sequential set C as cycle output.}\\ \\ \texttt{for}\ (x, y, w_{xy}) \gets |E|\\ \qquad\texttt{if}\ \text{dis}[y] \lt \text{dis}[x] + w_{xy}\\ \qquad\qquad c \gets y \\ \qquad\qquad \texttt{iterate}\ |V| \ \text{times}\\ \qquad\qquad\qquad c \gets \text{pre}[c]\\ \\ \qquad\qquad C \gets \lbrace c \rbrace \\ \qquad\qquad p \gets \text{pre}[c] \\ \\ \qquad\qquad\texttt{loop if}\ p \neq c\\ \qquad\qquad\qquad C \gets p\\ \qquad\qquad\qquad p \gets \text{pre}[p]\\ \\ \qquad\qquad \texttt{reverse}\ C\\ \qquad\qquad\text{exit with}\ C \end{array}\]实现
pub struct SPBellmanFord<'a> {
g: &'a Graph,
/// shortest path weight
src: usize,
spw: M1<usize, isize>,
//// shortest path paths
pre: M1<usize, usize>,
}
impl<'a> SPBellmanFord<'a> {
pub fn new(g: &'a Graph, src: usize) -> Result<Self, Vec<usize>> {
let (spw, pre) = sp_bellman_ford(g, src)?;
Ok(Self { g, src, spw, pre })
}
pub fn query(&self, dst: usize) -> (isize, Vec<usize>) {
(get!(self.spw => dst), pre_to_path!(dst, &self.pre))
}
}
fn sp_bellman_ford(
g: &Graph,
src: usize,
) -> Result<(M1<usize, isize>, M1<usize, usize>), Vec<usize>> {
let mut pre = M1::new();
let mut dis = M1::new();
let n = g.vertexs().count();
set!(dis => src => 0);
for _ in 1..=n-1 {
for (u, v, w) in g.edges() {
if let Some(dis_u) = getopt!(dis => u) {
if getopt!(dis => v).is_none() || dis_u + w < get!(dis => v) {
set!(dis => v => dis_u + w);
set!(pre => v => u);
}
}
}
}
// 探测负环
for (u, v, w) in g.edges() {
if let Some(dis_u) = getopt!(dis => u) {
if getopt!(dis => v).is_none() || dis_u + w < get!(dis => v) {
// negative cycle found!
let mut c = v;
// 确保在环上
for _ in 1..=n {
c = get!(pre => c);
}
return Err(install_cycle(c, &pre));
}
}
}
Ok((dis, pre))
}
时间复杂度
作为单源点算法，时间复杂度 $O(nm)$ ，如果求全源最短路径，就执行 $n$ 次该算法，那么就变成 $O(n^2m)$ 。
这个时间复杂度显然不太妙，因为根据联通图的稀疏程度有 $\vert V\vert \leqslant \vert E \vert \leqslant \vert V\vert ^2$ ，事实上原始的 Bellman-Ford 算法是本文介绍的这几个算法里最慢的，下面我们会介绍它的一个广为人知的变体即所谓的 “SPFA“ 算法。这个改进算法虽然没有改变最坏时间复杂度，但在实际运行中对于随机图的表现相当好。
so-called ‘SPFA’ 算法
这个 Bellman-Ford 的改进算法在 OI 界可谓大名鼎鼎，对于随机图的实际运行很快，而且实现方便。它是中国的研究员提出的，被认为本质上是 Tarjan 的图上广度优先遍历的一般化版本2 ，但我也看不出两者在算法思想上有什么直接的关系。
算法思想
‘SPFA’ 的改进在于观察到每一轮用于“松弛“操作的边都是上一轮更新过的点连接的边。这很好理解，回到算式 $ \text{dis}[y] = \texttt{min}(\text{dis}[y],\ \text{dis}[x] + w_{xy})$ ，如果上一轮 $\text{dis}[x]$ 没有变，那么这一轮 $\text{dis}[y]$ 也就不会变。
这样的话，
- 从源点开始，把它加入等待的集合 $R$ ；
- 每次从 $R$ 中取出一个点，遍历更新过的点连接的边，把其中更新的点加入 $R$ 中；
- 当 $R$ 为空时，算法终止
伪代码
对于图 $G=(V, E)$ ，源点 $s$ ：
\[\begin{array}{l} R \gets \lbrace s \rbrace\\ \\ \texttt{loop if}\ R\ \neq \varnothing \\ \qquad\ x \gets R\\ \qquad\texttt{for}\ (x, y, w_{wy})\ \texttt{in}\ \lbrace e\ |\ e[0]=x,\ e \in |E| \rbrace \\ \qquad\qquad\text{dis}[y] = \texttt{min}(\text{dis}[y],\ \text{dis}[x] + w_{xy})\\ \qquad\qquad R \gets y \end{array}\]路径构造同原始 Bellman-Ford 算法相同。
负环探测
负环探测由于没有全部边的迭代，因此有一点区别
有两种方法：
- 使用一个集合维护每个点经过的边数，显然最多不超过 $n-1$ 条，否则一定存在负环；
- 每迭代完 $n$ 个点，就检查一下pre数组，是否展开后超过 $n-1$ 条路径
第二种方法虽然最坏时间复杂度和第一种相同，但3在稀疏图和随机图情况下，可以天差地别般更快地检测到负环 。
另外对于第一种方法，使用 FILO 的栈结构显然有助于更快地找到负环。
实现
pub struct SPFA<'a> {
g: &'a Graph,
/// shortest path weight
src: usize,
spw: M1<usize, isize>,
//// shortest path paths
pre: M1<usize, usize>,
}
impl<'a> SPFA<'a> {
pub fn new(g: &'a Graph, src: usize) -> Result<Self, Vec<usize>> {
let (spw, pre) = sp_fa_early_termination(g, src)?;
Ok(Self { g, src, spw, pre })
}
pub fn query(&self, dst: usize) -> (isize, Vec<usize>) {
(get!(self.spw => dst), pre_to_path!(dst, &self.pre))
}
}
pub fn sp_fa_early_termination(
g: &Graph,
src: usize,
) -> Result<(M1<usize, isize>, M1<usize, usize>), Vec<usize>> {
let mut pre = M1::new();
let mut dis = M1::new();
let n = g.vertexs().count();
set!(dis => src => 0);
let mut vis = HashSet::new(); // 避免把重复元素入栈
let mut stack = vec![src]; // R set
let mut i = 0;
while let Some(u) = stack.pop() {
vis.remove(&u);
for v in get!(g.e => u => vec![]) {
// 无向图不存在这条路径
if !g.dir && getopt!(pre => u) == Some(v) {
continue;
}
// 如果不可达，那就直接跳过
if let Some(dis_u) = getopt!(dis => u) {
if getopt!(dis => v).is_none() ||
dis_u + get!(g.w => (u, v)) < get!(dis => v)
{
set!(dis => v => dis_u + get!(g.w => (u, v)));
set!(pre => v => u);
// 检测负环
i += 1;
if i == n {
if let Some(cycle) = detect_negative_cycle(n, v, &pre) {
return Err(cycle);
}
i = 0;
}
if !vis.contains(&v) {
stack.push(v);
vis.insert(v);
}
}
}
}
}
Ok((dis, pre))
}
时间复杂度
最坏时间复杂度不变，仍是 $O(nm)$ ，但实际运行是很好的（相对于其他能处理负边权的算法）。另外对于特定情况的一些进一步的优化，主要是关于如何根据有关条件把点加到对头还是队尾，这里就不展开了。
但接下来介绍的是有限制条件的更快算法：Dijkstra 算法 。
Dijkstra 算法
/ˈdaɪkstrəz/
算法思想
说是 Dijkstra 和妻子逛商场的时候花 20 分钟想出来的寻找到几个不同商场的最短路的方法4 ，是一种自然想到的利用非负权边的缩放性质进行快速查找的（单源）算法。
回顾前面的两个算法：
Floyd 算法（全源）是 $\text{dis}[u][v] = \text{min}(\text{dis}[u][v],\ \text{dis}[u][k]+\text{dis}[k][v])$
Bellman-Ford 算法（单源）是 $\text{dis}[v] = \text{min}(\text{dis}[v],\ \text{dis}[u]+w_{uv})$
它们都是基于直接的全路径的比较，适用于包括负权边在内的各种情况，而 Dijkstra 算法则利用了非负权边的缩放性质，在非负权图上可以算得更快。
考虑对于图 $G$ （有向强连通），设源点为 $s$ ，由于非负权重的性质，距离 $s$ 最近的点一定是与 $s$ 直接相邻的点，其次是与 $s$ 间隔为 $1$ 的点，再其次是间隔为 $2$ 的点，等等；并且有 $k \geqslant 1$ 条边的某个点 $d$ 的最短路径一定由某个最短路径为 $k-1$ 的点 $d’$ 的最短路径和边 $d’d$ 组成。
这样从 $s$ 的直接邻居开始，按照边的权重从小到大的顺序来求解，并用每个解去更新它邻近点到 $s$ 的距离，就可以按不减序得到 $s$ 到每个点的最短路径。
伪代码
对于图 $G=(V, E)$ ，源点 $s$ ：
\[\begin{array}{l} \texttt{let}\ \text{dis}[x]\ \text{as shortest path's distance from}\ s\ \text{to}\ x \\ \texttt{let}\ w_{xy}\ \text{as edge weight from}\ x\ \text{to}\ y\\ \\ \texttt{for}\ x \gets |V|\\ \qquad \texttt{if}\ x = s\\ \qquad\qquad \text{dis}[x] \gets 0\\ \qquad \texttt{elif}\ (s,x) \in |E|\\ \qquad\qquad \text{dis}[x]=w_{sx} \\ \qquad \texttt{else}\\ \qquad\qquad \text{dis}[x] = \infty\\ \\ T \gets |V|\\ \\ \texttt{loop if}\ T \neq \varnothing\\ \qquad u \gets \text{min}(T) \text{ by dis}[u] \\ \\ \qquad\texttt{for}\ (x, y)\ \texttt{in}\ \lbrace e\ |\ e[0]=u,\ \ e[1] \in T,\ e \in |E| \rbrace \\ \qquad\qquad \text{dis}[y] = \texttt{min}(\text{dis}[y],\ \text{dis}[x] + w_{xy}) \end{array}\]路径构造由于是对边的“松弛“，所以仍然采用 $\text{pre}$ 数组构造。
实现
用上前面实现的 d-ary 堆 来优化算法
pub struct SPDijkstra<'a> {
g: &'a Graph,
src: usize,
spw: M1<usize, isize>,
pre: M1<usize, usize>,
}
impl<'a> SPDijkstra<'a> {
pub fn new(g: &'a Graph, src: usize) -> Self {
let (spw, pre) = sp_dijkstra(g, src);
Self { g, src, spw, pre }
}
pub fn query(&self, dst: usize) -> (isize, Vec<usize>) {
(get!(self.spw => dst), pre_to_path!(dst, &self.pre))
}
}
fn sp_dijkstra(
g: &Graph,
src: usize,
) -> (HashMap<usize, isize>, HashMap<usize, usize>) {
let mut pre = HashMap::new();
let mut dis_m1 = HashMap::new();
let mut dis = dary::DaryHeap::<3, _, _>::new();
dis.insert(src, 0);
while let Some((u, dis_u)) = dis.pop_item() {
set!(dis_m1 => u => dis_u);
for v in get!(g.e => u) {
if !dis_m1.contains_key(&v) {
let w = dis_u + get!(g.w => (u, v));
let maybe_dis_v = dis.get(&v).cloned();
if maybe_dis_v.is_none() || w < maybe_dis_v.unwrap() {
dis.insert(v, w);
set!(pre => v => u);
}
}
}
}
(dis_m1, pre)
}
使用简单堆
上述实现是严格按照定义，使用了一个规整的支持 decrease_key 的堆，但是在数据规模不大的时候也可以在简单堆上插入新值来替代实现。
fn sp_dijkstra2(
g: &Graph,
src: usize,
) -> (HashMap<usize, isize>, HashMap<usize, usize>) {
let mut pre = HashMap::new();
let mut dis_m1 = HashMap::new();
let mut dis = sdary::DaryHeap::<3, _>::new();
dis.push((0, src));
while let Some((dis_u, u)) = dis.pop() {
if dis_m1.contains_key(&u) { continue }
set!(dis_m1 => u => dis_u);
for v in get!(g.e => u) {
if dis_m1.contains_key(&v) { continue }
let w: isize = dis_u + get!(g.w => (u, v));
let maybe_dis_v = dis_m1.get(&v).cloned();
if maybe_dis_v.is_none() || w < maybe_dis_v.unwrap() {
dis.push((w, v));
set!(pre => v => u);
}
}
}
(dis_m1, pre)
}
时间复杂度
作为单源点算法，在使用 d-ary 堆优化并使用惰性初始化策略的情况下，时间复杂度为 $\text{dis}$ 排序 + 边松弛等于 $O(1) + O(m) = O(m)$ 。
如果计算全源最短路径，就是 $O(nm)$ 。
相比前面算法直接在乘区上少了一个 $n$ ，可以说非常优秀了！
不过 Dijkstra 毕竟受限于非负权边的图，如何利用它的高效，改善含负权边的图的全源最短路径 $O(n^3)$ 的计算效率？ 这就是接下来的Johnson 算法做的事情。
Johnson 算法
算法思想
基本想法是通过重新调整边的权重，使得每条边的权重不小于 $0$ ，并且保持每对儿点的最短路径不会因此受到影响。
我们采取这样一种方法，对于图 $G=(V, E)$ ，用“势能”标记 $G$ 中的每个点：
- 建立基准线，增加一个特殊的点 $q$ ，使得 $q$ 到 $G$ 中每一个点都有一条边，权重为一个固定值 $c \geqslant 0$ （具体值无所谓，只是用来建立基准，选取一个非负数只是为了避免出现额外的负边导致出现不必要的负环）；
- 运行一次以 $q$ 为源点的 Bellman-Ford 算法（当然我们要用我们最爱的 ‘SPFA’ 算法），以每个点到 $q$ 的最短距离 $h$ 为它的“势能”，原 $G$ 上每条边 $(u, v)$ 的权重都加上 $u\rightarrow v$ 两点的“势能”差，也就是 $h(u) - h(v)$
这样同时满足了两个要求：
- 对于G上任意两点 $x$ , $y$ ，$G$ 上每条从 $x$ 到 $y$ 的路径，不管中间经过了多少个点，它们的最终权重和都增加了一个固定值，也就是 $h(x) -h(y)$ ，也就是这种调整不会影响任意点对的最短路径的判定；
- 并且由于源点 $q$ 的最短路径的性质 $h[v] \leqslant h[u] + w_{uv}$ 也就是 $w_{uv} + h[u] - h[v] \geqslant 0$ ，也就是所有边都变成了负值
直接在重新平衡权重的图上做 $n$ 次 Dijkstra 算法，就得到了全源的最短路径。当然查询最短路径的权重和时，要把加上的“势能”减去，也就是 $-(h[u]-h[v])$
实现
路径构造是 $\text{pre}$ 数组，负环探测是利用 Bellman-Ford 算法
pub struct SPJohnson<'a> {
g: &'a Graph,
h: M1<usize, isize>,
spw: M2<usize, usize, isize>,
//// shortest paths
sppre: M2<usize, usize, usize>,
}
impl<'a> SPJohnson<'a> {
pub fn new(g: &'a Graph) -> Result<Self, (Graph, Vec<usize>)> {
let (h, spw, sppre) = sp_johnson(g)?;
Ok(Self { g, h, spw, sppre })
}
/// (total_weight, (src), .. , k1, k2, .. dst)
pub fn query(&self, src: usize, dst: usize) -> (isize, Vec<usize>) {
(
get!(self.spw => (src, dst)) - get!(self.h => src)
+ get!(self.h => dst),
pre_to_path!(dst, self.sppre.0.get(&src).unwrap()),
)
}
}
fn sp_johnson(
g: &Graph,
) -> Result<
(
M1<usize, isize>,
M2<usize, usize, isize>,
M2<usize, usize, usize>,
),
(Graph, Vec<usize>),
> {
/* Create a new map with special node q*/
let mut g2 = g.clone();
let mut vertexs: Vec<usize> = g2.vertexs().collect();
vertexs.sort_unstable();
let q = *vertexs.last().unwrap() + 1;
for v in vertexs.iter().cloned() {
set!(g2.w => (q, v) => 0);
apush!(g2.e => q => v);
}
/* Using SPFA dst calc h((q, v)) */
let h = match sp_fa(&g2, q) {
Ok((h, _)) => h,
Err(cycle) => return Err((g2, cycle)),
};
/* Reweight */
for (u, v, w) in g.edges() {
set!(g2.w => (u, v) => w + get!(h => u) - get!(h => v));
}
/* Calc spw and spp usign Dijkstra */
let mut spw = M2::<usize, usize, isize>::new();
let mut sppre = M2::<usize, usize, usize>::new();
for v in vertexs {
let (sspw, sspp) = sp_dijkstra(&g2, v);
set!(spw => v => sspw);
set!(sppre => v => sspp);
}
Ok((h, spw, sppre))
}
以上算法也可以直接适用于无向图的情况。
值得说明的是，一般来说，对于邻接矩阵的实现，无向图是一条边的两端各保存一次，比如边 $a - b$ 保存为 $(a,b)$ 和 $(b,a)$ 。但这里特殊地在于，即使是无向图，虚点 $q$ 到源图所有点的路径也是单向的而不是双向的，因为不会有以 $q$ 为起点的查询；反过来，如果为无向图设置了从其他点到 $q$ 的反向边，就会在查询的时候引入实际不存在的边，导致错误的结果。
时间复杂度
$O(nm) + O(nm) = O(nm)$ ，这样在负权图上也实现了最坏时间复杂度为 $O(nm)$ 的最短路径算法！
注解
