数据结构与算法 / 技术文章
为什么 Dijkstra 不能处理负权边
标准 Dijkstra 每轮选出当前估计距离最小的未确定顶点,并把该距离定为最终值。所有边权非负时,这个贪心步骤有证明。允许负边后,即使图中没有环,也可能先确定了一个随后还能变短的顶点。
非负边权如何保证确定距离
设这一轮选中的顶点是 ,它的当前估计值为 。沿一条从源点到 的最短路,取第一个未确定顶点 。它的前驱已经确定,前驱出队时已经松弛了通向 的边,因此 不大于该路径到 的前缀代价。
边权非负时,从 继续到 不会减少代价,所以这段前缀代价不大于完整最短路的代价。另一方面,算法选择了未确定顶点中估计最小的 ,因此 。估计值本身来自一条已发现的实际路径,不能小于真正的最短距离。这些不等式合起来迫使 等于最短距离。起点距离为零是这个归纳的起始条件。
三个顶点已经足够构造反例
考虑有向边 权重 2、 权重 5、 权重 −4。从 开始,算法会按 2 先确定 ,再按 5 处理 。但是 的总代价为 。加入 权重 1 后,这个错误还会传到后继 。正确距离分别是 、。
一些错误实现会允许松弛时回写已确定顶点的数组值,却永远不会重新处理该顶点。此时最终打印的 可能碰巧正确, 仍沿用早先的错误估计 3。只观察 会漏掉问题。
Bellman-Ford 怎样处理负边和负环
Bellman-Ford 反复遍历边进行松弛。对已可达的 ,如果 ,就更新 。经过第 轮,至多使用 条边的候选路径已得到考虑。对存在有限最短距离的顶点,可以选一条不重复顶点的最短路,因此 轮足够。
之后再扫描一次。若可达边还能降低某些距离,就从这些下降位置继续沿有向边标记:能从源点先到负环再到达的顶点,没有有限最短距离。其他可达顶点仍可有有限答案。源点无法到达的负环与本次单源结果无关。
用 Python 对照三种行为
下例的邻接表列出所有顶点,所有边权为整数。为了隔离问题,故意给 Dijkstra 传入含负边的图。两个演示变体只在是否允许回写已确定顶点上不同,它们都不会再次传播该顶点的距离。
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]}")输出中,冻结式给出 ;只回写的版本得到 ;Bellman-Ford 得到 。第二张图中, 被标为 -inf, 仍为 3。 所在的负环从 不可达,所以它们保持 inf。
按图和边权选算法
| 条件 | 常用方法 | 依据 |
|---|---|---|
| 单源,所有相关边权非负 | Dijkstra | 每次取出的最小估计距离可以确定 |
| 单源,有负边的一般有向图 | Bellman-Ford | 多轮松弛,可检测从源点可达的负环 |
| 有向无环图 | 按拓扑顺序松弛 | 前驱先处理,允许负边 |
上面的线性选点 Dijkstra 用于教学。稀疏的非负权图可用优先队列减少选点开销。遇到负边时,先确认题目对有向性、可达性和负环的定义,再决定需要报告一个有限距离、不可达,还是可通过负环无限降低。
证明与实现可参考 Princeton 最短路径讲义和 MIT Bellman-Ford 讲义。