Dijkstra 最短路

图

说明

反复确定当前距离最小的顶点；只适用于非负边权。

分析

dist 记录目前已知的最短距离，每轮固定尚未处理且距离最小的顶点，再尝试松弛其出边。非负权重保证固定后的距离不会再变小。

图解推演

正文先固定距离为 0 的顶点 0，松弛得到 dist[1]=2；再固定 1，得到 dist[2]=5。补充反例：若 0→A=2、0→B=5、B→A=−4，A 会被过早固定为 2，实际应为 1。非负边是正确性前提，不能只把负数也塞进同一实现。

查看图表代码

适用前提与边界

示例使用简单的 O(V²+E) 扫描；大型稀疏图可用堆降低选点成本。

示例输入与调用

fmt.Println(Dijkstra([][]Edge{{{To: 1, Weight: 2}}, {{To: 2, Weight: 3}}, {}}, 0))

运行输出

[0 2 5]

完整 Go 示例

package main

import "fmt"

type Edge struct{ To, Weight int }

func Dijkstra(g [][]Edge, start int) []int {
	inf := int(^uint(0) >> 1)
	dist := make([]int, len(g))
	used := make([]bool, len(g))
	for i := range dist {
		dist[i] = inf
	}
	dist[start] = 0
	for range g {
		v := -1
		for i := range g {
			if !used[i] && (v < 0 || dist[i] < dist[v]) {
				v = i
			}
		}
		if v < 0 || dist[v] == inf {
			break
		}
		used[v] = true
		for _, e := range g[v] {
			if dist[v]+e.Weight < dist[e.To] {
				dist[e.To] = dist[v] + e.Weight
			}
		}
	}
	return dist
}

func main() {
	fmt.Println(Dijkstra([][]Edge{{{To: 1, Weight: 2}}, {{To: 2, Weight: 3}}, {}}, 0))
}