单源最短路径

一句话说明

单源最短路的核心不是先背算法名，而是先看边权长什么样，因为边权类型直接决定算法。

先用一张表做算法分流

图的类型	优先算法
无权图 / 每条边代价相同	BFS
边权只有 0/1	0-1 BFS
所有边权非负	Dijkstra
存在负权边	Bellman-Ford

这张表比死记模板更重要。

动画演示

（附件 dijkstra-relax.svg 未随站点发布）

看这个动画时先抓住一个事实

Dijkstra 不是“把所有边一次算完”，而是每次先确认当前全局最近的点，再用它去更新邻居。

为什么边权决定算法

无权图

每走一条边代价都一样，所以：

最短路 = 最少边数

因此按层推进的 BFS 就成立。

0/1 权图

距离变化只可能：

• 不变
• 增加 1

这时用 0-1 BFS 的双端队列就够了。

非负权图

Dijkstra 的核心不变量是：

当前从堆里弹出的最小距离节点，它的最短路已经最终确定。

这件事依赖“边权不能为负”。

负权图

一旦存在负权边，某个点后面仍可能被进一步拉低，Dijkstra 的前提就破了。
这时要用 Bellman-Ford 这类“反复松弛”的方案。

Go 代码：无权图最短路 BFS

func ShortestPathBFS(graph [][]int, start int) []int {
    dist := make([]int, len(graph))
    for i := range dist {
        dist[i] = -1
    }
 
    dist[start] = 0
    queue := []int{start}
 
    for len(queue) > 0 {
        node := queue[0]
        queue = queue[1:]
 
        for _, next := range graph[node] {
            if dist[next] != -1 {
                continue
            }
            dist[next] = dist[node] + 1
            queue = append(queue, next)
        }
    }
 
    return dist
}

Go 代码：Dijkstra

type Edge struct {
    To     int
    Weight int
}
 
type State struct {
    Node int
    Dist int
}
 
type MinHeap []State
 
func (h MinHeap) Len() int           { return len(h) }
func (h MinHeap) Less(i, j int) bool { return h[i].Dist < h[j].Dist }
func (h MinHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
 
func (h *MinHeap) Push(x any) {
    *h = append(*h, x.(State))
}
 
func (h *MinHeap) Pop() any {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[:n-1]
    return x
}
 
func Dijkstra(graph [][]Edge, start int) []int {
    const inf = int(1e18)
 
    dist := make([]int, len(graph))
    for i := range dist {
        dist[i] = inf
    }
    dist[start] = 0
 
    h := &MinHeap{{Node: start, Dist: 0}}
    heap.Init(h)
 
    for h.Len() > 0 {
        cur := heap.Pop(h).(State)
        if cur.Dist > dist[cur.Node] {
            continue
        }
 
        for _, e := range graph[cur.Node] {
            candidate := cur.Dist + e.Weight
            if candidate >= dist[e.To] {
                continue
            }
            dist[e.To] = candidate
            heap.Push(h, State{Node: e.To, Dist: candidate})
        }
    }
 
    return dist
}

为什么会有“过期堆元素”

同一个点可能多次被更新并重复进堆。
真正有效的只有当前这次：

cur.Dist == dist[cur.Node]

更旧、更大的记录就是过期状态，直接跳过即可。

Go 代码：Bellman-Ford

type DirectedEdge struct {
    From   int
    To     int
    Weight int
}
 
func BellmanFord(edges []DirectedEdge, n, start int) ([]int, bool) {
    const inf = int(1e18)
 
    dist := make([]int, n)
    for i := range dist {
        dist[i] = inf
    }
    dist[start] = 0
 
    for i := 0; i < n-1; i++ {
        updated := false
        for _, e := range edges {
            if dist[e.From] == inf {
                continue
            }
            candidate := dist[e.From] + e.Weight
            if candidate >= dist[e.To] {
                continue
            }
            dist[e.To] = candidate
            updated = true
        }
        if !updated {
            break
        }
    }
 
    hasNegativeCycle := false
    for _, e := range edges {
        if dist[e.From] != inf && dist[e.From]+e.Weight < dist[e.To] {
            hasNegativeCycle = true
            break
        }
    }
 
    return dist, hasNegativeCycle
}

为什么 Bellman-Ford 要做 n-1 轮

因为一条不含环的最短路径，最多只会经过 n-1 条边。
每松弛一轮，就相当于允许答案再多走一条边。

常见题型

• 最少几步：BFS
• 边权只有 0/1：0-1 BFS
• 网络延迟、最小花费：Dijkstra
• 有负权、限制中转次数：Bellman-Ford 变形

易错点

单源最短路最容易错的地方

• Dijkstra 不能处理负权边。
• BFS 只适用于等权边，不是所有最短路题都能套。
• Bellman-Ford 做“限制边数”时，常常要用临时数组，避免一轮内连锁更新。
• dist 初始化要统一，起点必须先置 0。

复杂度

算法	时间复杂度	空间复杂度	适用条件
BFS	O(V + E)	O(V)	无权图
0-1 BFS	O(V + E)	O(V)	0/1 权图
Dijkstra	O((V + E)\log V)	O(V)	非负权图
Bellman-Ford	O(VE)	O(V)	可含负权边

相关主题

• Dijkstra算法
• 0-1 BFS
• DFS 与 BFS

---

返回：图算法