【数据结构】图论最短路圣器：Floyd算法如何用双矩阵征服负权图？

穿越负权迷雾：Floyd算法如何解锁全图最短路径？​​

大家好，很高兴又和大家见面啦！！！

你是否曾为Dijkstra算法在负权图前折戟而苦恼？这位单源最短路径的王者虽能高效征服正权图，却对负权边束手无策——当图上出现“补贴路径”（负权值）时，Dijkstra的贪心策略将彻底失效！

而今天登场的图灵奖得主​​Floyd算法​​，正为此而生！它用动态规划的三重循环（复杂度O(丨V丨³），以惊人的简洁性完成两大壮举： 1️⃣ ​​暴力求取全源最短路径​​：同时计算图中任意两点的最短距离 2️⃣ ​​完美驾驭负权图​​：轻松化解Dijkstra的致命弱点（除负权环外）

透过递推矩阵的魔法，你将看到： ▸ 初始邻接矩阵如何在中转点催化下层层蜕变（含分步图解） ▸ 路径矩阵如何像侦探般记录关键前驱节点 ▸ C语言实现如何用双矩阵破译路径密码 ▸ 负权环检测为何是算法必备的安全阀

文末更奉上​​三大算法对决表​​，助你秒选最佳路径方案！​​点击揭开全源最短路径的终极奥秘→​

一、Floyd算法

Floyd算法是由罗伯特·弗洛伊德（Robert·W·Floyd）提出，用于解决所有顶点之间的最短路径问题。

罗伯特·弗洛伊德（Robert·W·Floyd）:

• 1978年图灵奖得主
• 提出了Floyd算法（Floyd-Warshall算法）
• 提出了堆排序算法

1.1 算法思想

Floyd算法使用动态规划的思想，将求解每一对顶点之间的最短路径分解为多个阶段进行求解：

• 对于n个顶点的图G，求任意一对顶点 V_i->V_jV_0 阶段：允许在 V_0 中转，再次获取各顶点之间的最短路径 V_1 阶段：允许在 V_0、V_1 中转，再次获取各顶点之间的最短路径 \cdots V_{n-1}阶段：允许在 V_0、V_1、\cdots、V_{n-1} 中转，再次获取各顶点之间的最短路径

为了更好的说明该算法的思想，下面我们以有向图G为例，介绍一下整个算法的执行过程：

graph LR
a--6-->b--4-->c--5-->a
b--10-->a--13-->c

在这个图中，包含3个顶点和5条弧：

• |V| = {a, b, c}
• |E| = {\<a, b, 6>, <a, c, 13>, \ <b, a, 10>, <b, c, 4>, \ <c, a, 5>\}

在Floyd算法执行的过程中，算法每一次执行，都会递推产生一个 3 阶方阵序列：

• 初始阶段，各顶点之间的路径默认没有中转点： 点 V_i 与点 V_j 之间连通，则从点 V_i 到点 V_j 的弧 <v_i, v_j>V_i 与点 V_j 之间不连通，则默认这两个顶点之间的路径长度为 \infty 初始阶段生成的 3 阶方阵如下所示：

$$ {初始阶段方阵V^{(-1)}}= \begin{bmatrix} & | & a &|& b&| & c&| \ — & — & — &—& —&— & —&—\ a & | & 0&|& 6&| & 13&| \ — & — & — &—& —&— & —&—\ b & | & 10 &|& 0&| & 4&| \ — & — & — &—& —&— & —&—\ c & | & 5 &|& \infty &| & 0&| \end{bmatrix} $$

• V_0阶段，各顶点之间借助 a 为中转点，继续查找各顶点之间的最短路径： 点 a 到点 b 借助顶点 a 为中转点，没有更优路径 点 a 到点 c 借助顶点 a 为中转点，没有更优路径 点 b 到点 a 借助顶点 a 为中转点，没有更优路径 点 b 到点 c 借助顶点 a 为中转点，没有更优路径 点 c 到点 a 借助顶点 a 为中转点，没有更优路径 点 c 到点 b 借助顶点 a为中转点，存在更优路径 <c, a, b, 11>V_0 阶段生成的 3 阶方阵如下所示：

$$ {V_0阶段方阵V^{(0)}}= \begin{bmatrix} & | & a &|& b&| & c&| \ — & — & — &—& —&— & —&—\ a & | & 0&|& 6&| & 13&| \ — & — & — &—& —&— & —&—\ b & | & 10 &|& 0&| & 4&| \ — & — & — &—& —&— & —&—\ c & | & 5 &|& \color{red}11 &| & 0&| \end{bmatrix} $$

• V_1阶段，各顶点之间借助 a 为中转点，继续查找各顶点之间的最短路径： 点 a 到点 b 借助顶点 a、b 为中转点，没有更优路径 点 a 到点 c 借助顶点 a、b 为中转点，存在更优路径 <a, b, c, 10>b 到点 a 借助顶点 a、b 为中转点，没有更优路径 点 b 到点 c 借助顶点 a、b 为中转点，没有更优路径 点 c 到点 a 借助顶点 a、b为中转点，没有更优路径 点 c 到点 b 借助顶点 a、b为中转点，没有更优路径 V_1 阶段生成的 3 阶方阵如下所示：

$$ {V_1阶段方阵V^{(1)}}= \begin{bmatrix} & | & a &|& b&| & c&| \ — & — & — &—& —&— & —&—\ a & | & 0&|& 6&| & \color{red}10&| \ — & — & — &—& —&— & —&—\ b & | & 10 &|& 0&| & 4&| \ — & — & — &—& —&— & —&—\ c & | & 5 &|& \color{red} 11&| & 0&| \end{bmatrix} $$

• V_2阶段，各顶点之间借助 a 为中转点，继续查找各顶点之间的最短路径： 点 a 到点 b 借助顶点 a、b、c 为中转点，没有更优路径 点 a 到点 c 借助顶点 a、b、c 为中转点，没有更优路径 点 b 到点 a 借助顶点 a、b、c 为中转点，存在更优路径 <b, c, a, 9>b 到点 c 借助顶点 a、b、c 为中转点，没有更优路径 点 c 到点 a 借助顶点 a、b、c为中转点，没有更优路径 点 c 到点 b 借助顶点 a、b、c为中转点，没有更优路径 V_2 阶段生成的 3 阶方阵如下所示：

$$ {V_2阶段方阵V^{(2)}}= \begin{bmatrix} & | & a &|& b&| & c&| \ — & — & — &—& —&— & —&—\ a & | & 0&|& 6&| & \color{red}10&| \ — & — & — &—& —&— & —&—\ b & | & \color{red}9 &|& 0&| & 4&| \ — & — & — &—& —&— & —&—\ c & | & 5 &|& \color{red} 11&| & 0&| \end{bmatrix} $$

到此为止，我们就完成了该图G中所有顶点之间的最短路径的获取；

1.2 算法逻辑

在上述的过程中，我们不难发现，整个Floyd算法在执行的过程中，实际上就是在维护一个大小为 |V| × |V| 的二维数组，或者说是图G的邻接矩阵；

为了更加清晰的获取到各点之间的准确路径，我们还可以再增加一个记录路径的矩阵path[][]，该矩阵的功能就是记录从点 V_i 到点 V_j 时途径的中转点，即最短路径中点 V_j 的前驱顶点；

算法的整个执行过程，实际上就是在遍历图G的邻接矩阵，只不过我们需要遍历 |V| 次，每一次遍历都相当于将点 V_k 作为中转点，去查找是否存在更短的路径；

算法的C语言实现如下所示：

void Floyd(AMGraph* g,int*** A,int*** path) {
	// 创建递推矩阵A与路径矩阵path
	*A = (int**)calloc(g->ver_num, sizeof(int*));
	assert(*A);
	*path = (int**)calloc(g->ver_num, sizeof(int*));
	assert(*path);
	for (int i = 0; i < g->ver_num; i++) {
		(*A)[i] = (int*)calloc(g->ver_num, sizeof(int));
		assert((*A)[i]);
		(*path)[i] = (int*)calloc(g->ver_num, sizeof(int));
		assert((*path)[i]);
	}
	// 初始阶段
	for (int i = 0; i < g->ver_num; i++) {
		for (int j = 0; j < g->ver_num; j++) {
			(*A)[i][j] = g->edge_matrix[i][j];
			// 路径存在，记录当前路径的前驱顶点
			if (i != j && (*A)[i][j] != INT_MAX) {
				(*path)[i][j] = i;
			}
			// 路径不存在，则初始化为-1
			else {
				(*path)[i][j] = -1;
			}
		}
	}
	// 递推阶段——以点K为中转点
	for (int k = 0; k < g->ver_num; k++) {
		// 遍历矩阵
		for (int i = 0; i < g->ver_num; i++) {
			for (int j = 0; j < g->ver_num; j++) {
				// 当前距离大于以点k为中转点的路径长度
				if ((*A)[i][k] != INT_MAX && (*A)[k][j] != INT_MAX && ((*A)[i][j] > (*A)[i][k] + (*A)[k][j])) {
					(*A)[i][j] = (*A)[i][k] + (*A)[k][j];	// 更新点i到点j的路径长度
					(*path)[i][j] = (*path)[k][j];			// 更新该路径上点j的前驱顶点信息
				}
			}
		}
	}
}

1.3 算法评价

该算法实现的方式其时间复杂度和空间复杂度分别为：

• 时间复杂度：T(N) = O(|V|^3)
• 空间复杂度：S(N) = O(|V|^2)

可以看到算法中最主要的时间消耗在于递推的过程：

• 遍历一趟矩阵需要 O(|V|^2) 的时间复杂度
• 总共需要遍历 |V| 趟

而算法的主要空间消耗在于对递推矩阵 A[][] 和路径矩阵path[][]的空间上，为了完整的记录所有结点的信息，因此，这两个矩阵的大小均为 |V|^2

1.4 算法限制

在上述的实现中，并不能完整的展示Floyd算法，主要原因是因为该算法无法处理负权值回路：

graph LR
a--"-9"-->b--"2"-->c--"5"-->a

在上图中，如果我们要求顶点b到顶点b的最短路径，显然我们每走一次路径 <b, c, a, b>

	// 检测负权环
	for (int i = 0; i < g->ver_num; i++) {
		if ((*A)[i][i] < 0) {
			printf("该图中存在负权环");
			return;
		}
	}

我这里对负权环的处理是采取的打印提示的方式，当然也可以选择别的方式，只要能够对负权环进行一个正确的检测即可。

二、三种算法对比

现在我们已经介绍完了处理最短路径问题的三种算法：BFS、Dijkstra、Floyd，下面我们就从六个维度来对比一下这三个算法的区别：

在实际的问题中，我们可以根据自己的需求，选择合适的算法来处理最短路径问题；

🌟结语

通过本文的探索，我们揭开了Floyd算法的神秘面纱： 🔹 三重循环的优雅暴力：以 O(丨V丨^3) 时间复杂度征服全源最短路径问题 🔹 动态规划的智慧结晶：通过递推矩阵的巧妙迭代，层层解锁最优路径 🔹 负权图的破壁者：打破Dijkstra算法局限，轻松驾驭负权边（除负权环外） 🔹 双矩阵的完美协奏：A矩阵记录距离，path矩阵回溯路径，实现路径溯源

📚 下一篇预告 在图论的奇妙世界中，我们将迎来新的伙伴： 🔥 《有向无环图：表达式的终极优化引擎》

• 揭秘如何用DAG实现表达式树的重构
• 探索公共子表达式消除的图解法
• 图解拓扑排序如何实现无环表达式优化
• 直击编译器中表达式优化的核心技术！