Floyd-Warshall算法详解（Go语言实现多源最短路径）

Floyd-Warshall算法原理

Floyd-Warshall算法的核心思想是动态规划。它通过逐步引入中间顶点，不断更新任意两点间的最短距离。

假设我们有一个图 G，包含 n 个顶点。我们用 dist[i][j] 表示从顶点 i 到顶点 j 的当前已知最短距离。

算法初始化时，dist[i][j] 被设置为：

• 如果 i == j，则 dist[i][j] = 0；
• 如果 i 和 j 之间有直接边，则 dist[i][j] = 边的权重；
• 否则，dist[i][j] = 无穷大（表示暂时不可达）。

然后，算法依次考虑每一个顶点 k（从 0 到 n-1）作为“中转站”，检查是否可以通过 k 来缩短 i 到 j 的路径：

if dist[i][k] + dist[k][j] < dist[i][j] {    dist[i][j] = dist[i][k] + dist[k][j]}

经过 n 轮这样的更新后，dist 矩阵就包含了所有顶点对之间的最短路径长度。

Go语言实现Floyd-Warshall算法

下面我们用Go语言来完整实现这个算法。我们将使用一个二维切片表示图，并处理正权、负权（但不能有负权环）的情况。

package mainimport (	"fmt"	"math")const INF = math.MaxInt32 / 2 // 防止加法溢出// floydWarshall 实现Floyd-Warshall算法func floydWarshall(graph [][]int) [][]int {	n := len(graph)	// 创建距离矩阵的副本	dist := make([][]int, n)	for i := range dist {		dist[i] = make([]int, n)		copy(dist[i], graph[i])	}	// 核心三重循环	for k := 0; k < n; k++ {		for i := 0; i < n; i++ {			for j := 0; j < n; j++ {				// 如果经过k能缩短i到j的距离，则更新				if dist[i][k] != INF && dist[k][j] != INF &&					dist[i][k]+dist[k][j] < dist[i][j] {					dist[i][j] = dist[i][k] + dist[k][j]				}			}		}	}	return dist}func main() {	// 示例图：4个顶点	graph := [][]int{		{0, 3, INF, 7},		{8, 0, 2, INF},		{5, INF, 0, 1},		{2, INF, INF, 0},	}	dist := floydWarshall(graph)	fmt.Println("所有顶点对之间的最短路径：")	for i := 0; i < len(dist); i++ {		for j := 0; j < len(dist[i]); j++ {			if dist[i][j] == INF {				fmt.Printf("%7s", "INF")			} else {				fmt.Printf("%7d", dist[i][j])			}		}		fmt.Println()	}}

算法复杂度与适用场景

- 时间复杂度：O(n³)，其中 n 是顶点数。由于是三重嵌套循环，适合顶点数量不太大的图（通常 n ≤ 500）。

- 空间复杂度：O(n²)，用于存储距离矩阵。

Floyd-Warshall算法的优势在于代码简洁、能处理负权边（但不能有负权环），并且一次性得到所有点对的最短路径。如果你正在学习Go语言图算法，这是一个非常值得掌握的基础算法。

总结

本文详细介绍了Floyd-Warshall算法的原理，并用Go语言实现了完整的多源最短路径求解过程。无论你是算法初学者还是Go开发者，希望这篇教程都能帮助你理解这一经典算法。记住，掌握全源最短路径的求解方法，将为你在图论和实际工程问题中打下坚实基础！