7 z3 @5 x Q3 K6 ^Bellman-Ford 算法能够处理带有负权边的图,但不能处理负权回路。它通过放松操作逐步更新从源节点到所有其他节点的最短路径。 . F5 Z r1 [: Q. w* G+ v: I f) [4 o) q f$ l3 a### 原理步骤 / S8 i9 e7 ^3 z. i3 T2 M3 H) t 0 a* R Z8 h: Z5 r1. **初始化**:3 _: H) h6 U7 n0 b
- 设置源节点到自己的距离为0,其他节点为无穷大。 3 r" v& p P3 z& u$ B4 |8 k+ ], S0 q# g+ \$ E
2. **松弛操作**:9 _8 s+ C. o9 O
- 对所有边进行松弛操作,循环(V-1)次(V为节点数),尝试更新每个边的距离。 ( u1 z9 T4 o: i# e5 J+ d+ A( U& f. q ^8 L' [6 ?9 {1 e; W
3. **检查负权回路**:9 @1 n( T7 {! P; i- b/ W C' q' D
- 再次对所有边进行一次松弛检查,如果有边的距离仍能被更新,则说明图中存在负权回路。 / G T' V+ q% T: d 1 b7 b6 ^8 l" q% _0 r; Z### 示例代码0 x N- U" w. k7 g
1 o" \6 X4 D; |! N```python 2 L. T k7 d! Ddef bellman_ford(graph, start): # V3 P* i5 i# q! T* y, D0 t # 初始化距离) t2 L4 S$ J6 n% R
distances = {node: float('inf') for node in graph} / ~" J. _$ {0 O distances[start] = 0: N9 b3 R0 l2 G& V* ?- P
! M, _& I# g6 y" O* o" C# f # 松弛操作 + O; |) c7 ?1 S" w. N9 m/ t for _ in range(len(graph) - 1): ' n9 Y# @2 G# O' {& J( I for u in graph: . k" l; ]+ |0 W$ b% ? for v, weight in graph[u].items(): j: K; ^- @. P4 J7 d& g if distances[u] + weight < distances[v]: 4 ^7 \( S7 T: d7 }( ? distances[v] = distances[u] + weight 2 K" B$ D. L; q8 G , R2 d6 ?8 l! s+ W M # 检查负权回路# {7 @5 Z3 i8 x+ P, F
for u in graph:& `8 Y% {6 Q7 e; H+ I
for v, weight in graph[u].items(): $ F1 R2 u2 i1 r8 ^0 }" L if distances[u] + weight < distances[v]: 0 v/ e/ V' r( f raise ValueError("Graph contains a negative weight cycle")- C$ T( {7 W7 b, G9 a
1 j5 q7 g- F/ Q2 X7 N3 s5 Z, f return distances * y6 n" {" |" o8 c$ ? . S) X4 d c8 h' r# 示例图(带有负权边) ! }5 N! K; a! n0 C! g, H9 z- O* [graph_with_negative_weight = {* P0 b4 k' M7 Z% c- I- ~! T
'A': {'B': 1, 'C': 4}, - \8 W! H9 g# I3 f 'B': {'C': -3, 'D': 2}, 3 Y, S; c) x) n$ P' o5 v 'C': {}, & g0 }9 Y% Z* k- T+ e5 f4 `, ] 'D': {'A': -1} 9 j0 n; v2 u, t}* w% }9 m! s8 y+ r