算法——所有节点对的最短路径：Floyd-Warshall算法、Johnson算法

前言

前面介绍了单源最短路径问题，本文是介绍所有节点对的最短路径问题，首先我们会想到用前面所介绍的知识来求解该问题，根据不同类型的图可以用一下几种方法求解：

若无权重的图，则可以使用 $|V|$ 次BFS，时间复杂度是 $O(V^{2}+VE)$ ;
若为非负权重边的图，则可以使用 $|V|$ 次Dijkstra算法，不同的优先队列实现得到不同的时间复杂度：①线性数组， $O(V^{3}+VE)=O(V^{3})$ 。②二叉堆， $O(VElgV)$ ,在稀疏图的情况下是一个较大的改进。③斐波那契堆， $O(V^{2}lgV+VE)$ ;
若含有负权重边的图，则可以使用 $|V|$ 次Bellman-Ford算法，稠密的情况下时间复杂度是为 $O(V^{4})$ ；

为了降低时间复杂度，我们下面采用 Floyd-Warshall 算法和 Johnson 算法进行求解。

Floyd-Warshall算法

该算法的原理是动态规划，并且图 $G=(E,V)$ 的表示方式是邻接表矩阵。根据动态规划的求解步骤：

分析最优解结构；
递归定义最优解的值；
自底向上计算最优解的值；
根据计算出的最优解的值构造最优解；

使用该算法是可以存在负权值的边，但不能存在权值为负值的环路。在求解之前先介绍基本概念：

中间节点：简单路径 $p=\left \{ v_{1} ,v_{2},...,v_{l}\right.\left. \right \}$ 的中间节点是指路径 $p$ 上除节点 $v_{1}$ 和节点 $v_{l}$ 之外的任意节点，也就是处于集合 $\left \{ v_{2},v_{3},...,v_{l-1}\right.\left. \right \}$ 中的节点。

Floyd-Warshall算法的求解步骤：

最短路径结构（最优解结构）

假定图 $G=(E,V)$ 的所有节点为 $V=\left \{ \right.1,2,...,n\left. \right \}$ ，考虑其中一个子集 $\left \{ \right.1,2,...,k\left. \right \}$ , $k< n$ 的某个整数。对任意节点 $i,j\epsilon V$ ，考虑从节点 $i$ 到节点 $j$ 的所有中间节点均取自集合 $\left \{ \right.1,2,...,k\left. \right \}$ 的路径，并且设 $p$ 为其中权重最小的路径。Floyd-Warshall算法利用路径 $p$ 和从节点 $i$ 到节点 $j$ 之间中间节点均取自集合 $\left \{ 1,2,...,k-1\left. \right \} \right.$ 的最短路径之间的关系。该关系依赖于节点 $k$ 是否是路径 $p$ 上的一个中间节点。

若节点 $k$ 不是路径 $p$ 的中间节点，则路径 $p$ 上的中间节点都属于集合 $\left \{ 1,2,...,k-1\left. \right \} \right.$ 。因此，从节点 $i$ 到节点 $j$ 之间中间节点均取自集合 $\left \{ 1,2,...,k-1\left. \right \} \right.$ 的一条最短路径也是从节点 $i$ 到节点 $j$ 的所有中间节点均取自集合 $\left \{ \right.1,2,...,k\left. \right \}$ 的一条最短路径，即： $d_{ij}^{(k)}=d_{ij}^{(k-1)}$ ,其中 $d_{ij}^{(k)}$ 表示从节点 $i$ 到节点 $j$ 的所有中间节点均取自集合 $\left \{ \right.1,2,...,k\left. \right \}$ 的一条最短路径的权重。
若节点 $k$ 是路径 $p$ 的中间节点，则将路径 $p$ 分解为 $i\overset{p_{1}}{\rightarrow}k\overset{p_{2}}{\rightarrow}j$ ,因此， $p_{1}$ 是从节点 $i$ 到节点 $k$ 之间中间节点均取自集合 $\left \{ 1,2,...,k-1\left. \right \} \right.$ 的一条最短路径，， $p_{2}$ 是从节点 $k$ 到节点 $j$ 之间中间节点均取自集合 $\left \{ 1,2,...,k-1\left. \right \} \right.$ 的一条最短路径,即： $d_{i,j}^{(k)}=d_{i,k}^{(k-1)}+d_{k,j}^{(k-1)}$

最短路径的一个递归解（递归定义最优解的值）

根据上面的分析可得一个递归解：

$d_{i,j}^{(k)}=\left\{\begin{matrix} \varpi _{i,j}& \: \: if\, \, \, \, k=0\\ & \\ min(d_{i,j}^{(k-1)},d_{i,k}^{(k-1)}+d_{k,j}^{(k-1)})& \, \, if\, \, k\geq 1 \end{matrix}\right.$

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

根据递归公式计算出最短路径权重。计算伪代码如下：

FLOYD-WARSHALL(W)  
{  
    n = W.rows;  
    D(0) = W;  
    for(k = 1;k <= n;++k){  
        let D(k) = d[i,j](k) be a new n*n matrix;  
        for i = 1 to n  
            for j = 1 to n  
                d[i,j](k) = min(d[i,j](k-1), d[i,k](k-1)+ d[k,j](k-1) )  
    }  
    return D(n);  
}

构造一条最短路径

我们选择在计算最短路径权值矩阵的 $D^{(k)}$ ，同时计算前驱矩阵 $\Pi$ ，我们定义 $\pi _{i,j}^{(k)}$ 为从节点 $i$ 到节点 $j$ 之间中间节点均取自集合 $\left \{ 1,2,...,k-1\left. \right \} \right.$ 的最短路径上 $j$ 的前驱节点。 $\pi _{i,j}^{(k)}$ 的递归定义跟最短路径权重类似。

当 $k=0$ 时：

$\pi _{i,j}^{(0)}=\left\{\begin{matrix} NIL& \, \, \, if\, \, \, i=j\, \, \, \, or\, \, \, \varpi _{i,j}=\infty \\ & \\ i& \, \, \, if\, \, \, i\neq j\, \, \, and\, \, \, \varpi _{i,j}\neq \infty \end{matrix}\right.$

当 $k\geq 1$ 时：

$\pi _{i,j}^{(k)}=\left\{\begin{matrix} \pi _{i,j}^{(k-1)}& \, \, \, if\, \, \, d _{i,j}^{(k-1)}\leqslant d _{i,k}^{(k-1)}+d _{k,j}^{(k-1)} \\ & \\ \pi _{k,j}^{(k-1)}& \, \, \, if\, \, \,d _{i,j}^{(k-1)}> d _{i,k}^{(k-1)}+d _{k,j}^{(k-1)} \end{matrix}\right.$

计算过程只是在计算最短路径权重的基础上加上计算前驱矩阵的算法即可。伪代码如下：

FLOYD-WARSHALL(W)  
{  
    n = W.rows;  
    D(0) = W;
	TT(0) = 初始值
    for(k = 1;k <= n;++k){  
        let D(k) = d[i,j](k) be a new n*n matrix;  
		let TT(k) = π[i,j](k) be a new n*n matrix;
        for i = 1 to n  
            for j = 1 to n  
                d[i,j](k) = min(d[i,j](k-1), d[i,k](k-1)+ d[k,j](k-1) )  
				if d[i,j](k)== d[i,j](k-1)
					π[i,j](k) = π[i,j](k-1)
				else π[i,j](k) = π[k,j](k-1)
    }  
    return D(n),TT(n);  
}

Johnson算法

Johnson算法主要用于求稀疏图上的所有节点对的最短路径。其主体思想是利用重新赋予权值的方法把一个原问题带负权的图转化为权值非负的图。然后再对每个节点使用一次Dijkstra算法以求出所有节点对的最短路径。时间复杂度 $O(V^{2}lgV+VE)$ ;

重新赋予权值必须满足一下两个条件：

对于所有节点对 $u,v\epsilon V$ ，一条路径 $p$ 是在使用权值函数 $\omega$ 时从节点 $u$ 到节点 $v$ 的一条最短路径，当且仅当 $p$ 是在权值函数 $\omega ^{* }$ 时从节点 $u$ 到节点 $v$ 的一条最短路径。
对于所有的边 $(u,v)$ ，新的权值 $\omega ^{* }(u,v)$ 为非负值。

重新赋予权值不会改变最短路径，对于每条边 $(u,v)\epsilon V$ ，权值函数的关系为： $\omega ^{*}(u,v)=\omega (u,v)+h(u)-h(v)$ ，其中 $h(v)$ 为新添加节点 $s$ 到节点 $v$ 的最短路径；

Johnson算法的步骤：

在带有权重的有向原始图 $G=(E,V)$ 添加一个新节点 $s$ 使其成为新的图 $G^{*}=({E}',{V}')$ ，其中 ${V}'=V\cup \left \{ s \right \}$ ， ${E}'=E\cup \left \{ (s,v):v\epsilon V\right \}$ 对于原图的所有节点 $v\epsilon V$ ，使其到新节点的边权值为0，即 $\omega (s,v)=0$ ；
用Bellman-Ford算法检查所输入的图 $G^{*}=({E}',{V}')$ 是否包含权值为负的环路，若有打印不存在最短路径并退出，否则继续；
Bellman-Ford算法计算新节点 $s$ 到所有节点 $v\epsilon {V}'$ 的最短路径,所计算的节点最短路径就是 $h(v)$ 的值；
更新所有边 $(u,v)\epsilon {E}'$ 的权值，即计算 $\omega ^{*}(u,v)=\omega (u,v)+h(u)-h(v)$ ；
对已更新权值的图 $G=(E,V)$ 的每个节点进行一次Dijkstra算法，求出所有节点对的最短路径；

举例说明Johnson算法的实现步骤：若要计算图 $G=(E,V)$ 的所有节点对的最短路径；

若是直接按照Bellman-Ford算法计算某个节点的最短路径，则如下图所示：

根据Johnson算法的步骤，首先添加新节点 $s$ 使其成为新图 $G^{*}=({E}',{V}')$ ，如下图所示：

对扩展图 $G^{*}=({E}',{V}')$ 进行一次Bellman-Ford算法处理，得到以 $s$ 为源节点的最短路径，如下图所示：

根据上一步骤以 $s$ 为源节点的最短路径更新边的权值，按照公式： $\omega ^{*}(u,v)=\omega (u,v)+h(u)-h(v)$ 进行更新，如下图所示：

根据上一步骤更新边的权值，得到新权值的图 $G=(E,V)$ ，如下图所示：

对更新权值后的图的每个节点进行一次Dijkstra算法，即可求得所有节点对的最短路径；由于只是重复的过程，下图只给出其中一个节点的求解图，其他节点这里就不给出了；提示：这里节点 $v$ 里面标记的权值是 $\hat{\delta }(u,v)$ ，与原图最短路径的关系为： $\hat{\delta }(u,v)=\hat{\delta }(u,v)+h(v)-h(u)$

原文链接：https://blog.csdn.net/chenhanzhun/article/details/39084905