![算法笔记:Floyd-Warshall算法](/assets/imgs/bgs/26.png)
算法笔记:Floyd-Warshall算法
大约 1 分钟
算法笔记:Floyd-Warshall算法
哦哦,哦哦哦!
![好看的](/assets/imgs/bgs/27.png)
算法作用
在一张有N个节点的非负权值图中,以O(N^3)
的复杂度寻找每两个节点之间最短路径的长度的算法。
准备工作
要执行Floyd-Warshall算法,我们需要如下元素:
- 一张不存在负权环的,有
N
个节点的图G
。 - 一个
N * N
大小的邻接矩阵M
,用于表示每两个节点之间的最短距离。
算法步骤
- 将
M
中的所有值初始化为+INF. - 枚举
G
中的所有边<u, v, w>
(从u
到v
的,权值为w
的边);将M[u][v]
设为w
。 - 从
1
到N
枚举中间节点K
, 对于每一个K
:
从1
到N
枚举源节点S
与目标节点D
。对于每一个<S, D, K>
,有:M[S][D] = min(M[S][D], M[S][K] + M[K][D])
. - 当该三重循环结束,
M[i][j]
即为该有向图G中节点i
到节点j
的最短路径。
正确性证明
说明
如果一张图中存在负权环,那么该图中两点之间的最短路径不存在(可以无限次经过负权环)。