数据结构与算法 / 系统课时

Dijkstra 为什么要求非负边

Dijkstra 为什么要求非负边

Dijkstra 的关键不是“使用优先队列”,而是每次取出当前距离最小的未确定顶点后,就把它的最短距离永久确定。这个贪心结论只在边权非负时成立;一条负权边就可能让已经确定的顶点再次变得更短。

学习目标

  • 说明 Dijkstra 贪心正确性为什么依赖非负边权
  • 用最小反例观察负权边如何推翻已确定距离
  • 根据边权条件选择 Dijkstra、Bellman-Ford 或 DAG 最短路

贪心成立依赖什么

设当前从源点到顶点 u 的暂定距离最小,Dijkstra 会把 u 标记为已确定。若所有边权都不小于 0,那么任何尚未确定的顶点 v 都满足 dist[v] >= dist[u],再从 v 经过一条或多条非负边绕回 u,路径长度只会更大,不可能产生比 dist[u] 更短的新路径。

因此,Dijkstra 的核心不变量是:被确定的顶点以后不需要再次修改距离。优先队列只是更快地找到当前最小的暂定距离,并不是正确性的来源。

负权边破坏 Dijkstra 已确定距离

负权边怎样打破不变量

考虑源点 S 到 A 的直接边权为 2,到 B 的边权为 5,同时存在 B -> A、权重为 -4 的边。Dijkstra 会先取出距离为 2 的 A 并确定它,但真正的更短路径是 S -> B -> A,总长度为 1。

下面的程序把“确定后不再修改”的 Dijkstra 与 Bellman-Ford 放在同一个反例中运行。图中不存在负环,因此真正的最短距离是有定义的。

python
from math import inf
from heapq import heappop, heappush

def dijkstra_finalized(graph, source):
    dist = [inf] * len(graph)
    settled = [False] * len(graph)
    dist[source] = 0
    pq = [(0, source)]

    while pq:
        d, u = heappop(pq)
        if settled[u]:
            continue
        settled[u] = True

        for v, weight in graph[u]:
            if settled[v]:
                continue
            nd = d + weight
            if nd < dist[v]:
                dist[v] = nd
                heappush(pq, (nd, v))
    return dist

def bellman_ford(graph, source):
    n = len(graph)
    dist = [inf] * n
    dist[source] = 0
    edges = [
        (u, v, weight)
        for u, adj in enumerate(graph)
        for v, weight in adj
    ]

    for _ in range(n - 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
    return dist

if __name__ == '__main__':
    graph = [
        [(1, 2), (2, 5)],
        [],
        [(1, -4)],
    ]

    print('Dijkstra:', dijkstra_finalized(graph, 0))
    print('Bellman-Ford:', bellman_ford(graph, 0))

预期输出

text
Dijkstra: [0, 2, 5]
Bellman-Ford: [0, 1, 5]

这里的 A 是顶点 1。错误并不是优先队列实现细节造成的,而是算法已经依据贪心假设把距离 2 视为最终答案。若实现允许负边后再次处理已弹出的顶点,它已经放弃了 Dijkstra 的“确定一次”性质,也失去了原本的复杂度与正确性证明。

什么时候改用其他算法

只要从源点可达的边中可能出现负权,就不应再依赖 Dijkstra 的贪心证明。一般图中可用 Bellman-Ford,它还能检测从源点可达的负环;若图本身是 DAG,则可以按拓扑序松弛,即使存在负权边也能在线性时间内求最短路。

还要区分“负权边”和“负环”。负权边只是让 Dijkstra 的前提失效;可达负环则意味着可以反复绕环让路径长度不断减小,此时相关顶点不存在有限的最短距离。

判断是否能用 Dijkstra 时,最先检查的不是图有多大,而是所有相关边权是否非负。只要这个条件不成立,就应换用与图结构和边权条件匹配的算法。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

Dijkstra 为什么要求非负边

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

登录哪都通