全源最短路问题：Floyd算法详解【经典算法，限时免费】

最短路问题概述

最短路问题（Shortest Path Problem）是图论中一个经典的问题，旨在找到从一个顶点到另一个顶点的最短路径。

所给定的图可以是有向图（directed graph）也可以是无向图（undirected graph），并且边可以有权重（weights），即每条边有一个数值表示从一个顶点到另一个顶点的距离或成本。

最短路问题的常见变种包括：

1. 单源最短路径问题：找到从图中某个特定顶点到所有其他顶点的最短路径。
2. 单对最短路径问题：找到从图中某个特定顶点到另一个特定顶点的最短路径。
3. 全源最短路径问题：找到图中每对顶点之间的最短路径。

解决最短路问题通常有包含以下算法

1. Dijkstra算法：

• 定义：用于解决单源最短路径问题，适用于边权重非负的图。
• 原理：通过贪心策略，逐步选择具有最小估计距离的顶点，并更新其邻接顶点的距离。
• 时间复杂度：O((V + E) log V)，其中 V 是顶点数，E 是边数。

2. Bellman-Ford算法：

• 定义：用于解决单源最短路径问题，可以处理负权重的边。
• 原理：通过对所有边进行多次松弛操作，逐步逼近最短路径。
• 时间复杂度：O(VE)，其中 V 是顶点数，E 是边数。

3. Floyd算法：

• 定义：用于解决全源最短路径问题。
• 原理：通过动态规划的方式，逐步考虑每个顶点作为中间点，更新所有顶点对之间的最短路径。
• 时间复杂度：O(V^3)，其中 V 是顶点数。

本篇讲解主要介绍Floyd算法的原理以及应用

带边权的图的全源最短路径

对于以下无向图，我们能够看到图中包含了若干节点以及节点之间的边权

这里的边权可以简单理解为两个节点之间的距离

大部分题目（但不是绝对的）会用一个外层长度为n，内层长度为3的二维数组edges，来表示包含图。

其中n是整个图的边数，edges[i] = [start_i, end_i, w_i]，表示在第i条边中，start_i节点和end_i节点之间的距离为w_i。

譬如，上述无向图可以用以下二维数组edges来表示

edges = 
[
[0, 1, 2],
[0, 4, 8],
[1, 2, 3],
[1, 4, 2],
[2, 3, 1],
[3, 4, 1]
]

有几点需要注意：

1. n = len(edges) = 6 是该无向图的边数
2. 边edges[i]在edges中的顺序并不重要
3. 对于无向图而言，每一条边的起点start_i和终点end_i的顺序也不重要
4. 如果是一个有向图，可能存在一条边的起点和终点互换则边权值不相等的情况出现（在实际生活中表现为两点之间的路径存在单行道、红灯停留时间等等）

假设我们现在需要一个储存数据的结构，通过该结构能够快速查询图中任意两个点的最短路径，那么这个数据应该如何设计？

由于查询任意两个点之间的距离都必须知道这两个点的具体编号，容易想到可以设计如下的一个二维数组。

我们可以把这个二维数组称为dist，其中行索引为起点的编号（绿色），列索引为终点的编号（黄色）。

dist是distance的缩写

如果我们要查询节点i到节点j的最短路径，我们直接通过查找dist[i][j]的值就可以得到。

譬如，dist[0][3]表示从节点0到节点3的最短路径为5。

在图中，我们容易看出这条路径是0 -> 1 -> 4 -> 3。

容易注意到二维数组dist存在以下特点

1. 该二维数组的内层和外层均为n（n行n列），表示该数组包含了n*n对节点的最短路径查询情况。
2. 该二维数组主对角线的值均为0（灰色部分），即存在dist[i][i] = 0成立，这表示任意一个节点到达它自身的最短路径是0（不需要任何其他路径）
3. 该二维数组沿主对角线对称，即存在dist[i][j] = dist[j][i]成立，表示从节点i出发到节点j的最短路径，和从节点j出发到节点i的最短路径是相同的。（这个特点仅对无向图成立）换句话说，只需要看这个二维数组的右上部分（紫色）或左下部分（白色），即可得知所有信息。

Floyd算法解决全源最短路问题

截止到目前，我们已经知道，解决全源最短路问题，要求我们得到的结果就是这个dist。

接下来努力的方向就是如何找到这个dist。

而Floyd算法就是基于动态规划思想，通过多次迭代找到这个二维数组dist的过程。

dist数组初始化

回到例子

edges = [
[0, 1, 2],
[0, 4, 8],
[1, 2, 3],
[1, 4, 2],
[2, 3, 1],
[3, 4, 1]
]

我们根据上述edges数组所给出的起始边情况，初始化dist数组。若

• 节点start_i和节点end_i在edges中是一条初始存在的边，则设置dist[start_i][end_i]为其对应的权值或距离w_i
• 节点start_i和节点end_i在edges中不是一条初始存在的边，则设置dist[start_i][end_i]为正无穷inf或一个极大的数，表示在初始边中，无法从start_i到达end_i
• 节点start_i和end_i相等的时候，则设置dist[start_i][end_i] = 0，即对角线上的0

其对应代码如下

from math import infdef Floyd(n, edges):dist = [[inf] * n for _ in range(n)]for start, end, w in edges:dist[start][end], dist[end][start] = w, wfor i in range(n):dist[i][i] = 0pass

dist数组迭代以及动态转移方程

由于初始化后dist数组中的数字仅仅代表着这些直接连接的边的长度，我们需要思考，如果我们把某些点作为桥梁（或称之为中间点）把某两个点连起来，那么会不会使得这两个点之间的最短路径相较于之前变得更短？

换句话说，假设我们选择节点k，作为节点i和节点j之间所经过的中间点，能否使得节点i和节点j之间的最短路径dist[i][j]变得更小？

譬如，考虑节点1作为节点0和节点4之间的中间点。

由于dist[0][1] = 2, dist[1][4] = 2，dist[0][4] = 8。

我们发现存在dist[0][1] + dist[1][4] < dist[0][4]成立。

这意味着，如果我们想从节点0出发到达节点4，走0 -> 1 -> 4这样的路径，会优于0 -> 4这样的路径。

所以，我们会将dist[0][4]修改为比之前更小的dist[0][1] + dist[1][4] = 4。

而在这之后，当我们涉及到以节点4作为中间节点去连接从节点0出发到其他节点（譬如节点3）的时候，就可以使用dist[0][4] = 4而不是dist[0][4] = 8来作为节点0到节点4的最短路径了。

随着这个例子的推出，Floyd算法的动态转移方程也就呼之欲出了。

假设我们选择节点k，作为节点i和节点j之间所经过的中间点。那么

$$dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j])$$

换句话说，当考虑经过中间点k能使得节点i和节点j之间的路径更短，则修改dist[i][j]为这个更短距离。

由于每一个节点都有可能成为另外任意两个节点的中间节点，为了不漏掉任何一个可能的中间节点，我们必须对所有的中间节点k进行遍历，并且在固定k的前提下，再次进行起点i和终点j的双重遍历。

其对应的代码为

def Floyd(n, edges):passfor k in range(n):for i in range(n):for j in range(n):dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])return dist

Floyd算法求解dist数组完整代码

python

def Floyd(n, edges):# 初始化dist二维数组，用一个大数代替infdist = [[100000] * n for _ in range(n)]# 初始化dist二维数组中的边为edges的起始边的情况for start, end, w in edges:dist[start][end], dist[end][start] = w, w# 初始化dist二维数组的对角线均为0for i in range(n):dist[i][i] = 0# 遍历中间节点k，每一个节点都有可能成为中间节点for k in range(n):# 遍历起始节点i，每一个节点都有可能成为起始节点for i in range(n):# 遍历终止节点j，每一个节点都有可能成为终止节点for j in range(n):# 动态转移方程dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])# 返回dist数组    return dist

java

import java.util.Arrays;public class Main {public static int[][] Floyd(int n, int[][] edges) {// 初始化dist二维数组，用一个大数代替infint[][] dist = new int[n][n];for (int[] row : dist) {Arrays.fill(row, 100000);}// 初始化dist二维数组中的边为edges的起始边的情况for (int[] edge : edges) {int start = edge[0];int end = edge[1];int w = edge[2];dist[start][end] = w;dist[end][start] = w;}// 初始化dist二维数组的对角线均为0for (int i = 0; i < n; i++) {dist[i][i] = 0;}// 遍历中间节点k，每一个节点都有可能成为中间节点for (int k = 0; k < n; k++) {// 遍历起始节点i，每一个节点都有可能成为起始节点for (int i = 0; i < n; i++) {// 遍历终止节点j，每一个节点都有可能成为终止节点for (int j = 0; j < n; j++) {// 动态转移方程dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);}}}// 返回dist数组return dist;}public static void main(String[] args) {// 初始化n和edges数组，可以自行进行修改和调整int n = 5;int[][] edges = {{0, 1, 2},{0, 4, 8},{1, 2, 3},{1, 4, 2},{2, 3, 1},{3, 4, 1}};// 调用Floyd函数得到dist最小距离矩阵int[][] dist = Floyd(n, edges);// 输出dist最小距离矩阵for (int[] row : dist) {for (int val : row) {System.out.print(val + " ");}System.out.println();}}
}

cpp

#include <iostream>
#include <vector>
#include <algorithm>using namespace std;vector<vector<int>> Floyd(int n, vector<vector<int>>& edges) {// 初始化dist二维数组，用一个大数代替infvector<vector<int>> dist(n, vector<int>(n, 100000));// 初始化dist二维数组中的边为edges的起始边的情况for (const auto& edge : edges) {int start = edge[0];int end = edge[1];int w = edge[2];dist[start][end] = w;dist[end][start] = w;}// 初始化dist二维数组的对角线均为0for (int i = 0; i < n; i++) {dist[i][i] = 0;}// 遍历中间节点k，每一个节点都有可能成为中间节点for (int k = 0; k < n; k++) {// 遍历起始节点i，每一个节点都有可能成为起始节点for (int i = 0; i < n; i++) {// 遍历终止节点j，每一个节点都有可能成为终止节点for (int j = 0; j < n; j++) {// 动态转移方程dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);}}}// 返回dist数组return dist;
}int main() {// 初始化n和edges数组，可以自行进行修改和调整int n = 5;vector<vector<int>> edges = {{0, 1, 2},{0, 4, 8},{1, 2, 3},{1, 4, 2},{2, 3, 1},{3, 4, 1}};// 调用Floyd函数得到dist最小距离矩阵vector<vector<int>> dist = Floyd(n, edges);// 输出dist最小距离矩阵for (const auto& row : dist) {for (int val : row) {cout << val << " ";}cout << endl;}return 0;
}

时空复杂度

时间复杂度：O(N^3)。三重循环所需时间复杂度。

空间复杂度：O(N^2)。最小距离矩阵dist所占空间。

其中N为节点数目。

*Floyd算法正确性证明

本处内容不做具体讲解，感兴趣的同学可以自行学习。

Floyd算法的核心是其动态转移方程

$$dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j])$$

该转移方程表示，如果通过顶点 k 作为中间点可以使 i 到 j 的路径更短，则更新 dist[i][j] 为 dist[i][k] + dist[k][j]。

证明过程

我们可以使用归纳法来证明Floyd算法的正确性。

初始情况

在初始情况下， dist[i][j] 被设定为以下几种情况之一：

1. 如果 i == j，则 dist[i][j] = 0。
2. 如果 i 和 j 之间有一条边，则 dist[i][j] 为该边的权重。
3. 否则， dist[i][j] 设为无穷大（inf），表示两点之间不可达。

这个初始化保证了在没有中间点的情况下，每对顶点 (i, j) 的最短路径是正确的。

归纳假设

假设在迭代到某个中间点 k 之前，dist[i][j] 表示从顶点 i 到顶点 j 的最短路径，且这个路径仅包含编号不大于 k-1 的中间点。

归纳步骤

对于每一对顶点 (i, j)，我们在考虑是否通过中间点 k 更新路径时有以下两种情况：

1. 不通过中间点 k：在这种情况下，最短路径长度保持为 dist[i][j]，即没有比原有路径更短的路径。
2. 通过中间点 k：如果通过 k 能够使路径更短，则路径长度应更新为 dist[i][k] + dist[k][j]。这是因为 dist[i][k] 是从 i 到 k 的最短路径长度，而 dist[k][j] 是从 k 到 j 的最短路径长度。

根据动态转移方程：

$$dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j])$$

我们选择较小的值来更新 dist[i][j]，确保 dist[i][j] 始终表示从 i 到 j 的最短路径长度。

终止条件

当所有顶点都作为中间点被考虑完毕后，dist[i][j] 就表示从 i 到 j 的最短路径长度，因为所有可能的中间点都已经被考虑在内。

完整证明

1. 初始条件正确：初始化阶段保证了直接路径的正确性。
2. 保持最优子结构性质：通过动态转移方程，我们在每一步中都选择最优解（较小的路径长度），确保子问题的解是最优的。
3. 正确性归纳：在迭代的每一步中，假设之前的所有步骤已经正确计算了路径长度，那么当前步骤也能正确更新路径长度，从而保证最终结果的正确性。

通过上述步骤，我们证明了Floyd算法的动态转移方程的正确性。该方程在每一步中都能够有效地更新最短路径长度，最终保证在所有中间点被考虑之后，dist[i][j] 表示从顶点 i 到顶点 j 的最短路径长度。

相关题目

LeetCode1334.阈值距离内邻居最少的城市

【最短路问题】2024D-快递员的烦恼