Dijkstra算法

What · 是什么

Dijkstra 算法是求解『非负权图』上单源最短路径的经典算法（由 E. W. Dijkstra 1956 年发现、1959 年发表）。维护两个集合：已确定最短路的点集 S 与未确定的点集 T；每次从 T 中取出当前 dis 最小的点 u 加入 S，并用 u 松弛其所有出边。用优先队列（堆）实现时复杂度 O((V+E)log V)，朴素 O(V²)。它要求所有边权非负，否则贪心的『当前最小即确定』不再成立。是竞赛中最常用的单源最短路算法，也是分层图、Johnson 全源、最小费用流等的子程序。

Why · 为什么

How · 实现

伪代码

# 堆优化 Dijkstra (无负权边)
def dijkstra(adj, s):
  INF = inf
  dis = [INF]*n; dis[s]=0
  pq = [(0, s)]
  while pq:
    d, u = heappop(pq)
    if d > dis[u]: continue      # 过时条目
    for v, w in adj[u]:
      if dis[v] > d + w:
        dis[v] = d + w
        heappush(pq, (dis[v], v))
  return dis

Python 实现

import heapq
from collections import defaultdict


def dijkstra(adj, s, n):
    """堆优化 Dijkstra. adj: 邻接表 adj[u]=[(v,w),...]; s: 起点; n: 点数.
    返回 dis 列表 (0-indexed); 不可达为 float('inf')。要求边权非负。"""
    INF = float('inf')
    dis = [INF] * n
    dis[s] = 0
    pq = [(0, s)]
    while pq:
        d, u = heapq.heappop(pq)
        if d > dis[u]:
            continue
        for v, w in adj[u]:
            nd = d + w
            if nd < dis[v]:
                dis[v] = nd
                heapq.heappush(pq, (nd, v))
    return dis


def dijkstra_path(adj, s, t, n):
    """额外重建路径: 返回 (dist, path); path 为从 s 到 t 的节点序列"""
    INF = float('inf')
    dis = [INF] * n
    pre = [-1] * n
    dis[s] = 0
    pq = [(0, s)]
    while pq:
        d, u = heapq.heappop(pq)
        if d > dis[u]:
            continue
        for v, w in adj[u]:
            nd = d + w
            if nd < dis[v]:
                dis[v] = nd
                pre[v] = u
                heapq.heappush(pq, (nd, v))
    if dis[t] == INF:
        return INF, []
    path = []
    cur = t
    while cur != -1:
        path.append(cur)
        cur = pre[cur]
    path.reverse()
    return dis[t], path


if __name__ == "__main__":
    # 手动构造: 0-1(2),0-2(5),1-3(1),2-3(2),1-2(1)
    adj = defaultdict(list)
    adj[0] = [(1, 2), (2, 5)]
    adj[1] = [(3, 1), (2, 1)]
    adj[2] = [(3, 2)]
    adj[3] = []
    dis = dijkstra(adj, 0, 4)
    assert dis[0] == 0 and dis[1] == 2 and dis[2] == 3 and dis[3] == 3, dis
    d, p = dijkstra_path(adj, 0, 3, 4)
    assert d == 3 and p == [0, 1, 3], (d, p)

    # 与 Floyd 交叉验证 (随机图)
    import random
    random.seed(7)
    for _ in range(200):
        n = random.randint(1, 8)
        g = defaultdict(list)
        dmat = [[float('inf')] * n for _ in range(n)]
        for i in range(n):
            dmat[i][i] = 0
        for i in range(n):
            for j in range(n):
                if i != j and random.random() < 0.3:
                    w = random.randint(1, 9)
                    g[i].append((j, w))
                    dmat[i][j] = w
        s = random.randrange(n)
        dis = dijkstra(g, s, n)
        # Floyd
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    dmat[i][j] = min(dmat[i][j], dmat[i][k] + dmat[k][j])
        for i in range(n):
            a = dis[i]
            b = dmat[s][i]
            if a == float('inf'):
                assert b == float('inf'), (a, b)
            else:
                assert a == b, (a, b)
    print("All tests passed.")

易错点

• 有负权边时结果错误且无提示——题面若未保证非负应改用 SPFA/Bellman-Ford
• 过时堆条目未检查 d > dis[u] 就继续松弛，导致重复处理/错误
• dis 用 float('inf') 时与 int 加法比较混合有隐患，建议统一大整数 INF
• 重边/自环需逐边松弛而非取 min 后建图（堆优化天然处理，但邻接表要都保留）
• 朴素实现每次 O(V) 找最小点，稠密图专用；堆优化在稀疏图才明显
• n 很大时 INF 要设 > 可能的最大路径和（如 n*maxw），用 1<<60 稳妥

例题

信源

• OI Wiki✓ https://oi-wiki.org/graph/shortest-path/
• CP-Algorithms✓ https://cp-algorithms.com/graph/dijkstra.html
• 书籍✓ CPH ch13 pp133-142