功能说明
Bellman-Ford 与 Dijkstra 的关键差别在于允许负权边：它对全部边做节点数减一轮松弛，因此能发现总权重为负的环。这一组函数接收节点列表、边列表和起点，返回距离表、前驱表以及可选的负环路径。前驱表可以直接还原从起点到任意节点的具体路线，适合带惩罚或折扣权重的路由、结算差额传播等场景。
当一轮松弛没有任何更新时会提前退出，在普通图上通常远快于最坏情况的 O(VE)。检测到负环后，距离值不再代表真实最短路径，调用方应拒绝该结果。
关键代码
核心循环外层最多执行 len(nodes) - 1 次，内层遍历所有边并比较 distance[source] + weight 与 distance[target]。发现负环时，从被再次松弛的目标出发，沿前驱指针走节点数步，必然停在环内；随后继续前进直到回到起点，反转即可得到环上的节点序列。shortest_path 从终点反向追溯前驱，若遇到 None 说明目标不可达。
使用注意
节点列表必须包含所有边的端点，否则会触发 KeyError。浮点权重会累积误差，金额场景应改用整数或 Decimal。负环检测只能发现从起点可达的环；不可达区域的权重不会参与比较。图中存在零权环不会误报，因为判定条件是严格小于。前驱表在负环场景下已被污染，不能再用来还原路径。节点数量为 1 时不会执行松弛，但仍会扫描负环。
验证方式
示例图从 A 出发，B 的 4.0 加上 B 到 C 的 -2.5 使 D 的最短距离为 4.5，路线为 A -> B -> C -> D。第二组数据包含 B 与 C 之间的双向负权，输出负环 B, C, B。可以再添加一个不可达节点，确认其距离保持 inf 且路径为空。
代码示例
from __future__ import annotations
from dataclasses import dataclass
@dataclass(frozen=True)
class Edge:
source: str
target: str
weight: float
def bellman_ford(
nodes: list[str],
edges: list[Edge],
start: str,
) -> tuple[dict[str, float], dict[str, str | None], list[str] | None]:
distance = {node: float("inf") for node in nodes}
previous: dict[str, str | None] = {node: None for node in nodes}
distance[start] = 0.0
for _ in range(len(nodes) - 1):
relaxed = False
for edge in edges:
candidate = distance[edge.source] + edge.weight
if candidate < distance[edge.target]:
distance[edge.target] = candidate
previous[edge.target] = edge.source
relaxed = True
if not relaxed:
break
return distance, previous, find_negative_cycle(nodes, edges, distance, previous)
def find_negative_cycle(
nodes: list[str],
edges: list[Edge],
distance: dict[str, float],
previous: dict[str, str | None],
) -> list[str] | None:
for edge in edges:
if distance[edge.source] + edge.weight < distance[edge.target]:
previous[edge.target] = edge.source
node = edge.target
for _ in range(len(nodes)):
node = previous[node] # type: ignore[assignment]
cycle = [node]
cursor = previous[node]
while cursor != node and cursor is not None:
cycle.append(cursor)
cursor = previous[cursor]
cycle.append(node)
cycle.reverse()
return cycle
return None
def shortest_path(previous: dict[str, str | None], start: str, target: str) -> list[str]:
path = [target]
cursor = target
while cursor != start:
parent = previous[cursor]
if parent is None:
return []
path.append(parent)
cursor = parent
path.reverse()
return path
def main() -> None:
nodes = ["A", "B", "C", "D"]
edges = [
Edge("A", "B", 4.0),
Edge("A", "C", 5.0),
Edge("B", "C", -2.5),
Edge("C", "D", 3.0),
Edge("B", "D", 6.0),
]
distance, previous, cycle = bellman_ford(nodes, edges, "A")
print("cycle:", cycle)
print("D cost:", distance["D"])
print("path:", " -> ".join(shortest_path(previous, "A", "D")))
risky = [Edge("A", "B", 1.0), Edge("B", "C", -1.0), Edge("C", "B", -1.0)]
_, _, cycle = bellman_ford(["A", "B", "C"], risky, "A")
print("negative cycle:", cycle)
if __name__ == "__main__":
main()