Floyd–Warshall 最短路

图

说明

逐个允许中转点来更新所有点对距离；时间 O(V³)。

分析

第 k 轮只允许前 k 个节点作为中转点，用 i→k→j 与现有 i→j 距离取较小值。三重循环得到所有点对的最短距离，适合顶点数较少且查询很多的图。

图解推演

在 0→1=2、1→2=3 的矩阵里，允许顶点 1 作中转后，dist[0][2] 从不可达变成 5。k 必须作为最外层，使每轮共享同一组允许的中转点。负边可以存在，但若出现 dist[v][v]<0，则存在负环，受其影响的点对没有有限最短路。

查看图表代码

适用前提与边界

需要用足够大的 inf 表示不可达，并避免相加溢出。

示例输入与调用

d := [][]int{{0, 2, 99}, {99, 0, 3}, {99, 99, 0}}
	FloydWarshall(d, 99)
	fmt.Println(d[0][2])

运行输出

5

完整 Go 示例

package main

import "fmt"

func FloydWarshall(d [][]int, inf int) {
	for k := range d {
		for i := range d {
			for j := range d {
				if d[i][k] != inf && d[k][j] != inf && d[i][k]+d[k][j] < d[i][j] {
					d[i][j] = d[i][k] + d[k][j]
				}
			}
		}
	}
}

func main() {
	d := [][]int{{0, 2, 99}, {99, 0, 3}, {99, 99, 0}}
	FloydWarshall(d, 99)
	fmt.Println(d[0][2])
}