Bellman–Ford 最短路

图

说明

对所有边最多松弛 V−1 轮；支持负边并可检测可达负环。

分析

第 k 轮结束后，至多经过 k 条边的最短路径均已覆盖；原地松弛还可能在同轮传播更远，因此最多 V−1 轮足以覆盖无环最短路径。再扫描一次若仍能改进，说明存在从起点可达的负权环。

图解推演

图中先把 0→1 的距离改为 2，再通过权重 −1 的边把 2 的距离改为 1。原地更新时一轮可能传播多条边；准确保证是第 k 轮后，至多 k 条边的最短路径已被覆盖。只有源点可达的负环才影响本次单源结果，不可达点必须先排除，不能拿 inf 参与松弛。

查看图表代码

适用前提与边界

算法允许负边，但时间 O(VE)，通常比 Dijkstra 慢。

示例输入与调用

distance, ok := BellmanFord(3, []Edge{{0, 1, 2}, {1, 2, -1}}, 0)
	fmt.Println(distance, ok)

运行输出

[0 2 1] true

完整 Go 示例

package main

import "fmt"

type Edge struct{ From, To, Weight int }

func BellmanFord(n int, edges []Edge, start int) ([]int, bool) {
	inf := int(^uint(0) >> 1)
	d := make([]int, n)
	for i := range d {
		d[i] = inf
	}
	d[start] = 0
	for i := 1; i < n; i++ {
		for _, e := range edges {
			if d[e.From] != inf && d[e.From]+e.Weight < d[e.To] {
				d[e.To] = d[e.From] + e.Weight
			}
		}
	}
	for _, e := range edges {
		if d[e.From] != inf && d[e.From]+e.Weight < d[e.To] {
			return d, false
		}
	}
	return d, true
}

func main() {
	distance, ok := BellmanFord(3, []Edge{{0, 1, 2}, {1, 2, -1}}, 0)
	fmt.Println(distance, ok)
}