数据结构与算法 / 系统课时
Dijkstra 为什么要求非负边
Dijkstra 为什么要求非负边
Dijkstra 的关键不是“使用优先队列”,而是每次取出当前距离最小的未确定顶点后,就把它的最短距离永久确定。这个贪心结论只在边权非负时成立;一条负权边就可能让已经确定的顶点再次变得更短。
学习目标
- 说明 Dijkstra 贪心正确性为什么依赖非负边权
- 用最小反例观察负权边如何推翻已确定距离
- 根据边权条件选择 Dijkstra、Bellman-Ford 或 DAG 最短路
贪心成立依赖什么
设当前从源点到顶点 u 的暂定距离最小,Dijkstra 会把 u 标记为已确定。若所有边权都不小于 0,那么任何尚未确定的顶点 v 都满足 dist[v] >= dist[u],再从 v 经过一条或多条非负边绕回 u,路径长度只会更大,不可能产生比 dist[u] 更短的新路径。
因此,Dijkstra 的核心不变量是:被确定的顶点以后不需要再次修改距离。优先队列只是更快地找到当前最小的暂定距离,并不是正确性的来源。

负权边怎样打破不变量
考虑源点 S 到 A 的直接边权为 2,到 B 的边权为 5,同时存在 B -> A、权重为 -4 的边。Dijkstra 会先取出距离为 2 的 A 并确定它,但真正的更短路径是 S -> B -> A,总长度为 1。
下面的程序把“确定后不再修改”的 Dijkstra 与 Bellman-Ford 放在同一个反例中运行。图中不存在负环,因此真正的最短距离是有定义的。
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))预期输出
Dijkstra: [0, 2, 5]
Bellman-Ford: [0, 1, 5]这里的 A 是顶点 1。错误并不是优先队列实现细节造成的,而是算法已经依据贪心假设把距离 2 视为最终答案。若实现允许负边后再次处理已弹出的顶点,它已经放弃了 Dijkstra 的“确定一次”性质,也失去了原本的复杂度与正确性证明。
什么时候改用其他算法
只要从源点可达的边中可能出现负权,就不应再依赖 Dijkstra 的贪心证明。一般图中可用 Bellman-Ford,它还能检测从源点可达的负环;若图本身是 DAG,则可以按拓扑序松弛,即使存在负权边也能在线性时间内求最短路。
还要区分“负权边”和“负环”。负权边只是让 Dijkstra 的前提失效;可达负环则意味着可以反复绕环让路径长度不断减小,此时相关顶点不存在有限的最短距离。
判断是否能用 Dijkstra 时,最先检查的不是图有多大,而是所有相关边权是否非负。只要这个条件不成立,就应换用与图结构和边权条件匹配的算法。