Floyd算法求解各顶点之间最短路径问题-Toy模板网

这篇具有很好参考价值的文章主要介绍了Floyd算法求解各顶点之间最短路径问题。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

一、Floyd算法

概述

Floyd算法，也称为Floyd-Warshall算法，是一种用于求解图中所有节点之间最短路径的算法。Floyd算法可以处理负权边的情况，但是不能处理负权环。
Floyd算法基于动态规划思想，通过一个二维数组记录从一个节点到另一个节点的最短路径长度。算法的核心思想是逐渐增加中间节点，如果在加入一个中间节点后能够获得更短的路径，则更新路径长度。经过n次迭代之后，最终可以得到图中任意两个节点之间的最短路径长度。

示例

初始状态

Floyd算法求解各顶点之间最短路径问题

如图：这是一个有三个顶点的有向图，矩阵A存储了两点之间的最短距离，在初始状态下就是一个邻接矩阵；矩阵pre记录了两点之间的最短路径中，加入的中转顶点。

以 $v_0$ 为中转点

初始状态	路径长度	加入中转点 $v_0$	路径长度	是否加入
$v_1$ -> $v_1$	0	$v_1$ -> $v_0$ -> $v_1$	10 + 6 = 16	×
$v_1$ -> $v_2$	4	$v_1$ -> $v_0$ -> $v_2$	10 + 13 = 23	×
$v_2$ -> $v_1$	$\infty$	$v_2$ -> $v_0$ -> $v_1$	5 + 6 =11	√
$v_2$ -> $v_2$	0	$v_2$ -> $v_0$ -> $v_2$	5 + 13 = 18	×

所以，在 $v_2$ -> $v_1$ 之间加入点 $v_0$ 作为中转。这里没有考虑在 $v_0$ -> $v_0$ 、 $v_0$ -> $v_1$ 、 $v_0$ -> $v_2$ 、 $v_1$ -> $v_0$ 、 $v_2$ -> $v_0$ 中加入 $v_0$ 作为中转，因为这没有意义；我们将计算得出的结果反映在下图中，将 $A^{(1)}$ [ $v_2$ ][ $v_1$ ]的值置为11，表示在加入 $v_0$ 作为中转之后，最短路径的长度由 $\infty$ 变为了11， $A^{(1)}$ [ $v_2$ ][ $v_1$ ]的值置为0，表示 $v_2$ 到 $v_1$ 这个路径路径中，加入了 $v_0$ 作为中转点。

Floyd算法求解各顶点之间最短路径问题

以 $v_1$ 为中转点

初始状态	路径长度	加入中转点 $v_0$	路径长度	是否加入
$v_0$ -> $v_0$	0	$v_0$ -> $v_1$ -> $v_0$	6 + 10 = 16	×
$v_0$ -> $v_2$	13	$v_0$ -> $v_1$ -> $v_2$	6 + 4 = 10	√
$v_2$ -> $v_0$	5	$v_2$ -> $v_1$ -> $v_0$	11 + 10 = 21	×
$v_2$ -> $v_2$	0	$v_2$ -> $v_1$ -> $v_2$	11 + 4 = 5	×

分析过程同上，结果如下图

Floyd算法求解各顶点之间最短路径问题

以 $v_2$ 为中转点

初始状态	路径长度	加入中转点 $v_0$	路径长度	是否加入
$v_0$ -> $v_0$	0	$v_0$ -> $v_2$ -> $v_0$	10 + 5 = 156	×
$v_0$ -> $v_1$	6	$v_0$ -> $v_2$ -> $v_1$	6 + 10 = 16	×
$v_1$ -> $v_0$	10	$v_1$ -> $v_2$ -> $v_0$	4 + 5 = 9	√
$v_1$ -> $v_2$	0	$v_1$ -> $v_2$ -> $v_1$	4 + 11 = 15	×

分析过程同上，结果如下图

Floyd算法求解各顶点之间最短路径问题

如何使用这两个矩阵呢？

例如，通过A，我知道 $v_0$ 到 $v_2$ 的最短路径长度是10，从pre可以知道，从 $v_0$ 到 $v_2$ 需要先从 $v_0$ 到 $v_1$ ，再从 $v_1$ 到 $v_2$ 。

6.时间复杂度和空间复杂度文章来源地址https://www.toymoban.com/news/detail-450010.html

时间复杂度	解释	空间复杂度	解释
O( $V\\|^3$ )	Floyd算法的执行过程是每次将一个顶点作为中转，\|V\|个顶点，需要执行\|V\|次相同的操作，在每次操作中，我们都需要遍历矩阵A，需要 $V\\|^2$ 的时间，所以总共需要O( $V\\|^3$ )	O( $V\\|^2$ )	在算法执行的过程中，需要借助两个数组，A和pre，两个数组都需要 $V\\|^2$ 的空间，所以空间复杂度是O( $V\\|^2$ )