Floyd算法求解各顶点之间最短路径问题
一、Floyd算法
一、Floyd算法
概述
Floyd算法，也称为Floyd-Warshall算法，是一种用于求解图中所有节点之间最短路径的算法。Floyd算法可以处理负权边的情况，但是不能处理负权环。 Floyd算法基于动态规划思想，通过一个二维数组记录从一个节点到另一个节点的最短路径长度。算法的核心思想是逐渐增加中间节点，如果在加入一个中间节点后能够获得更短的路径，则更新路径长度。经过n次迭代之后，最终可以得到图中任意两个节点之间的最短路径长度。
示例
初始状态
如图：这是一个有三个顶点的有向图，矩阵A存储了两点之间的最短距离，在初始状态下就是一个邻接矩阵；矩阵pre记录了两点之间的最短路径中，加入的中转顶点。
以
v
0
v_0
v0为中转点
初始状态路径长度加入中转点
v
0
v_0
v0路径长度是否加入
v
1
v_1
v1 ->
v
1
v_1
v10
v
1
v_1
v1 ->
v
0
v_0
v0 ->
v
1
v_1
v110 + 6 = 16×
v
1
v_1
v1 ->
v
2
v_2
v24
v
1
v_1
v1 ->
v
0
v_0
v0 ->
v
2
v_2
v210 + 13 = 23×
v
2
v_2
v2 ->
v
1
v_1
v1
∞
\infty
∞
v
2
v_2
v2 ->
v
0
v_0
v0 ->
v
1
v_1
v15 + 6 =11√
v
2
v_2
v2 ->
v
2
v_2
v20
v
2
v_2
v2 ->
v
0
v_0
v0 ->
v
2
v_2
v25 + 13 = 18×
所以，在
v
2
v_2
v2 ->
v
1
v_1
v1之间加入点
v
0
v_0
v0作为中转。这里没有考虑在
v
0
v_0
v0 ->
v
0
v_0
v0、
v
0
v_0
v0 ->
v
1
v_1
v1、
v
0
v_0
v0 ->
v
2
v_2
v2、
v
1
v_1
v1 ->
v
0
v_0
v0、
v
2
v_2
v2 ->
v
0
v_0
v0中加入
v
0
v_0
v0作为中转，因为这没有意义；我们将计算得出的结果反映在下图中，将
A
(
1
)
A^{(1)}
A(1)[
v
2
v_2
v2][
v
1
v_1
v1]的值置为11，表示在加入
v
0
v_0
v0作为中转之后，最短路径的长度由
∞
\infty
∞变为了11，
A
(
1
)
A^{(1)}
A(1)[
v
2
v_2
v2][
v
1
v_1
v1]的值置为0，表示
v
2
v_2
v2 到
v
1
v_1
v1这个路径路径中，加入了
v
0
v_0
v0作为中转点。
以
v
1
v_1
v1为中转点
初始状态路径长度加入中转点
v
0
v_0
v0路径长度是否加入
v
0
v_0
v0 ->
v
0
v_0
v00
v
0
v_0
v0 ->
v
1
v_1
v1 ->
v
0
v_0
v06 + 10 = 16×
v
0
v_0
v0 ->
v
2
v_2
v213
v
0
v_0
v0 ->
v
1
v_1
v1 ->
v
2
v_2
v26 + 4 = 10√
v
2
v_2
v2 ->
v
0
v_0
v05
v
2
v_2
v2 ->
v
1
v_1
v1 ->
v
0
v_0
v011 + 10 = 21×
v
2
v_2
v2 ->
v
2
v_2
v20
v
2
v_2
v2 ->
v
1
v_1
v1 ->
v
2
v_2
v211 + 4 = 5×
分析过程同上，结果如下图
以
v
2
v_2
v2为中转点
初始状态路径长度加入中转点
v
0
v_0
v0路径长度是否加入
v
0
v_0
v0 ->
v
0
v_0
v00
v
0
v_0
v0 ->
v
2
v_2
v2 ->
v
0
v_0
v010 + 5 = 156×
v
0
v_0
v0 ->
v
1
v_1
v16
v
0
v_0
v0 ->
v
2
v_2
v2 ->
v
1
v_1
v16 + 10 = 16×
v
1
v_1
v1 ->
v
0
v_0
v010
v
1
v_1
v1 ->
v
2
v_2
v2 ->
v
0
v_0
v04 + 5 = 9√
v
1
v_1
v1 ->
v
2
v_2
v20
v
1
v_1
v1 ->
v
2
v_2
v2 ->
v
1
v_1
v14 + 11 = 15×
分析过程同上，结果如下图
如何使用这两个矩阵呢？
例如，通过A，我知道
v
0
v_0
v0 到
v
2
v_2
v2的最短路径长度是10，从pre可以知道，从
v
0
v_0
v0 到
v
2
v_2
v2需要先从
v
0
v_0
v0 到
v
1
v_1
v1，再从
v
1
v_1
v1 到
v
2
v_2
v2。
6.时间复杂度和空间复杂度
时间复杂度解释空间复杂度解释O(
∥
V
∥
3
\|V\|^3
∥V∥3)Floyd算法的执行过程是每次将一个顶点作为中转，|V|个顶点，需要执行|V|次相同的操作，在每次操作中，我们都需要遍历矩阵A，需要
∥
V
∥
2
\|V\|^2
∥V∥2的时间，所以总共需要O(
∥
V
∥
3
\|V\|^3
∥V∥3)O(
∥
V
∥
2
\|V\|^2
∥V∥2)在算法执行的过程中，需要借助两个数组，A和pre，两个数组都需要
∥
V
∥
2
\|V\|^2
∥V∥2的空间，所以空间复杂度是O(
∥
V
∥
2
\|V\|^2
∥V∥2)
文章来源
您阅读本篇文章共花了：
发表评论