数据结构与算法 / 技术文章

为什么 Dijkstra 不能处理负权边

标准 Dijkstra 每轮选出当前估计距离最小的未确定顶点,并把该距离定为最终值。所有边权非负时,这个贪心步骤有证明。允许负边后,即使图中没有环,也可能先确定了一个随后还能变短的顶点。

非负边权如何保证确定距离

设这一轮选中的顶点是 uu,它的当前估计值为 d[u]d[u]。沿一条从源点到 uu 的最短路,取第一个未确定顶点 ww。它的前驱已经确定,前驱出队时已经松弛了通向 ww 的边,因此 d[w]d[w] 不大于该路径到 ww 的前缀代价。

边权非负时,从 ww 继续到 uu 不会减少代价,所以这段前缀代价不大于完整最短路的代价。另一方面,算法选择了未确定顶点中估计最小的 uu,因此 d[u]≤d[w]d[u]\le d[w]。估计值本身来自一条已发现的实际路径,不能小于真正的最短距离。这些不等式合起来迫使 d[u]d[u] 等于最短距离。起点距离为零是这个归纳的起始条件。

三个顶点已经足够构造反例

考虑有向边 A→BA\to B 权重 2、A→CA\to C 权重 5、C→BC\to B 权重 −4。从 AA 开始,算法会按 2 先确定 BB,再按 5 处理 CC。但是 A→C→BA\to C\to B 的总代价为 5−4=15-4=1。加入 B→DB\to D 权重 1 后,这个错误还会传到后继 DD。正确距离分别是 B=1B=1、D=2D=2。

一些错误实现会允许松弛时回写已确定顶点的数组值,却永远不会重新处理该顶点。此时最终打印的 BB 可能碰巧正确,DD 仍沿用早先的错误估计 3。只观察 BB 会漏掉问题。

Bellman-Ford 怎样处理负边和负环

Bellman-Ford 反复遍历边进行松弛。对已可达的 uu,如果 d[u]+w(u,v)<d[v]d[u]+w(u,v)<d[v],就更新 d[v]d[v]。经过第 kk 轮,至多使用 kk 条边的候选路径已得到考虑。对存在有限最短距离的顶点,可以选一条不重复顶点的最短路,因此 ∣V∣−1|V|-1 轮足够。

之后再扫描一次。若可达边还能降低某些距离,就从这些下降位置继续沿有向边标记:能从源点先到负环再到达的顶点,没有有限最短距离。其他可达顶点仍可有有限答案。源点无法到达的负环与本次单源结果无关。

用 Python 对照三种行为

下例的邻接表列出所有顶点,所有边权为整数。为了隔离问题,故意给 Dijkstra 传入含负边的图。两个演示变体只在是否允许回写已确定顶点上不同,它们都不会再次传播该顶点的距离。

python
from math import inf

def dijkstra_demo(graph, start, rewrite_settled=False):
    dist = dict.fromkeys(graph, inf)
    dist[start] = 0
    settled = set()
    while len(settled) < len(graph):
        u = min((node for node in graph if node not in settled), key=dist.get)
        if dist[u] == inf:
            break
        settled.add(u)
        for v, weight in graph[u]:
            if v not in settled or rewrite_settled:
                dist[v] = min(dist[v], dist[u] + weight)
    return dist

def bellman_ford(graph, start):
    dist = dict.fromkeys(graph, inf)
    dist[start] = 0
    edges = [(u, v, w) for u, neighbors in graph.items() for v, w in neighbors]

    for _ in range(len(graph) - 1):
        changed = False
        for u, v, weight in edges:
            if dist[u] != inf and dist[u] + weight < dist[v]:
                dist[v] = dist[u] + weight
                changed = True
        if not changed:
            break

    affected = {v for u, v, w in edges if dist[u] != inf and dist[u] + w < dist[v]}
    pending = list(affected)
    while pending:
        u = pending.pop()
        for v, _ in graph[u]:
            if v not in affected:
                affected.add(v)
                pending.append(v)
    for v in affected:
        dist[v] = -inf
    return dist

graph = {
    "A": [("B", 2), ("C", 5)],
    "B": [("D", 1)],
    "C": [("B", -4)],
    "D": [],
}
for label, result in (
    ("冻结", dijkstra_demo(graph, "A")),
    ("仅回写", dijkstra_demo(graph, "A", rewrite_settled=True)),
    ("Bellman-Ford", bellman_ford(graph, "A")),
):
    print(f"{label}: B={result['B']}, D={result['D']}")

cycles = {
    "S": [("A", 1), ("U", 3)],
    "A": [("B", -2)],
    "B": [("A", 1), ("T", 2)],
    "T": [],
    "U": [],
    "X": [("Y", -2)],
    "Y": [("X", 1)],
}
cycle_result = bellman_ford(cycles, "S")
for v in ("A", "B", "T", "U", "X", "Y"):
    print(f"{v}: {cycle_result[v]}")

输出中,冻结式给出 B=2,D=3B=2,D=3;只回写的版本得到 B=1,D=3B=1,D=3;Bellman-Ford 得到 B=1,D=2B=1,D=2。第二张图中,A,B,TA,B,T 被标为 -inf,UU 仍为 3。X,YX,Y 所在的负环从 SS 不可达,所以它们保持 inf。

按图和边权选算法

条件 常用方法 依据
单源,所有相关边权非负 Dijkstra 每次取出的最小估计距离可以确定
单源,有负边的一般有向图 Bellman-Ford 多轮松弛,可检测从源点可达的负环
有向无环图 按拓扑顺序松弛 前驱先处理,允许负边

上面的线性选点 Dijkstra 用于教学。稀疏的非负权图可用优先队列减少选点开销。遇到负边时,先确认题目对有向性、可达性和负环的定义,再决定需要报告一个有限距离、不可达,还是可通过负环无限降低。

证明与实现可参考 Princeton 最短路径讲义和 MIT Bellman-Ford 讲义。

目录与阅读设置

记录一个想法

为什么 Dijkstra 不能处理负权边

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通