在线时间 479 小时 最后登录 2026-4-17 注册时间 2023-7-11 听众数 4 收听数 0 能力 0 分 体力 7790 点 威望 0 点 阅读权限 255 积分 2923 相册 0 日志 0 记录 0 帖子 1171 主题 1186 精华 0 分享 0 好友 1
该用户从未签到
最短路径算法用于寻找图中两点之间的最短路径。这类算法在网络路由、地图导航、物流和许多其他应用中起到关键作用。常见的最短路径算法包括 Dijkstra 算法、Bellman-Ford 算法和 Floyd-Warshall 算法。下面将介绍这些算法的基本原理和具体实现。8 u* S& r) x( y r
) R" G5 x- P. U3 r7 \ ## 1. Dijkstra 算法
) x5 \, f2 J! ]( b( Q
7 b/ L4 U; d7 b ~. o Dijkstra 算法用于计算单源最短路径,有效于边权为非负数的图。它通过贪心策略逐步选择最短路径,从起点出发扩展到其他节点。0 d8 I+ V- ~' j) E
_% t4 b/ E) S# p ] ### 原理步骤' t( F, h5 c8 p7 d2 j/ r, l
: i3 Y8 H% Q7 e! Y9 R. ?
1. **初始化**:7 ~& F9 s" Y# z, S+ o( `
- 设置源节点到自己的距离为0,其他节点为无穷大(一般用 `inf` 表示)。
% b. T, p* M* t c0 U. t5 A2 W# d - 初始化一个空的优先队列,用于存储待处理的节点。
% ?4 B- q/ r7 c7 t a( ^6 P* ~1 m
+ O2 ~$ _, ?; [+ |4 D+ r* y 2. **处理节点**:
) o* _, d" t2 U$ i, O - 从优先队列中选取距离最小的节点作为当前节点。" R5 t+ P& a7 \" Z
- 更新当前节点的所有邻接节点的距离。如果新的距离更短,则更新并将邻接节点加入优先队列。
+ I) b/ J0 C# y) F5 s6 q& D4 Z " p n2 Z& j" G! M Z" D
3. **重复处理**:2 D- I3 M* O e9 k8 L
- 继续选择距离最小的节点,直到处理完所有节点或找到目标节点。
) `* S) L. ?7 {
9 f: e$ b' |3 V! t: F& K ### 示例代码! [4 {# R; q& I2 l' u! \
# v" \/ p7 _* ~& A: s1 w$ r ```python6 B! C1 U/ v! j& b
import heapq
. U( `5 y- }0 o8 ~0 K 4 p ?! Y% ?- K
def dijkstra(graph, start):' k# F! |! u+ Y4 Q
# 图的表示为字典,键为节点,值为邻接节点及其边权
' ?# I3 D, h) O6 V queue = []8 D/ s& d0 G: y
distances = {node: float('inf') for node in graph}
) h5 x4 B; U1 U' T8 o' d1 _ distances[start] = 0
; B6 b3 l* X( z( _# J heapq.heappush(queue, (0, start)) # (距离, 节点)
& k4 S9 K% B. c! F) Z6 v $ A# q9 u& S( o9 S# i$ ?
while queue:
. @# ~' o" V; N* B7 p current_distance, current_node = heapq.heappop(queue): g, c* n7 m8 A
5 J1 M1 |+ ~( f- ?# S/ b3 k
# 只处理当前节点的最短距离' Q5 t' Y6 _; y/ n3 d
if current_distance > distances[current_node]:
, l" Z3 e5 d$ Q/ l continue
I% B" p: b; U: h# t5 K, g" b ) h G6 j' x! J3 x6 d: ?- q
for neighbor, weight in graph[current_node].items():" V+ Z. A& I, I( E6 e' ?
distance = current_distance + weight1 N+ b# J3 ^: T8 k s
$ m5 E: S. z& B/ n7 Y
# 更新邻接节点的距离
( q8 j! R7 o c4 T' h if distance < distances[neighbor]:
% `9 I# Z2 O5 n; P4 m+ H7 |8 o distances[neighbor] = distance( V/ s3 ], w; T( T: g
heapq.heappush(queue, (distance, neighbor))3 G& D% ?- R% c0 r
; H% V! ?# K, L- M% `1 d return distances
0 S3 u, q5 f4 R, t3 m" n E : g* O! G" `# ?$ C- J% T
# 示例图
2 ~/ u' L7 E5 {, \1 j% T7 O: d4 G graph = {* g& H7 q! ?& j1 C# Q( I/ Y
'A': {'B': 1, 'C': 4},8 S- }, ?" j4 K0 d7 I! z
'B': {'A': 1, 'C': 2, 'D': 5},# j7 B8 K# m- O9 w1 z7 C0 T
'C': {'A': 4, 'B': 2, 'D': 1},
0 {6 t4 Q. ^( _ i1 F; E# Z 'D': {'B': 5, 'C': 1},! g8 b+ c7 S! U9 q6 G/ S
}
8 C# Q) j. D: ?& m1 S. \ 0 b% P8 L" ?1 o9 l. ~
start_node = 'A'+ g; X$ E5 X! x+ G5 h% @$ ^( P
shortest_paths = dijkstra(graph, start_node)
* J) \! ~9 o* `6 {) g% g$ `$ ^ print(shortest_paths) # {'A': 0, 'B': 1, 'C': 3, 'D': 4}; \# t3 j2 l% ]
```
2 _+ E" K. R z& t . b- R- r/ K6 m; `( q/ D
## 2. Bellman-Ford 算法/ V: f9 V1 }4 e
( ?: O, S9 E7 f3 ^2 }% x, O P Bellman-Ford 算法能够处理带有负权边的图,但不能处理负权回路。它通过放松操作逐步更新从源节点到所有其他节点的最短路径。' t" O3 B2 W4 \* n# ]5 P3 q
% ]# E# E" |4 ~! o ### 原理步骤& B$ a% n' w+ L" O" B) G) K
, j* ~ l$ K: D6 l6 \1 @
1. **初始化**:
+ r& }; h0 @ \ - 设置源节点到自己的距离为0,其他节点为无穷大。, [0 R1 v; D( H0 y5 U
! m% {3 o: w5 m8 p& S4 e 2. **松弛操作**:1 S3 d3 x4 ~) @7 o4 j8 {- ~/ L
- 对所有边进行松弛操作,循环(V-1)次(V为节点数),尝试更新每个边的距离。
% N& o) z$ q& E5 A
) I5 w! L/ z1 [ m 3. **检查负权回路**:
5 S9 q, r: B5 w% L. ^- G2 E - 再次对所有边进行一次松弛检查,如果有边的距离仍能被更新,则说明图中存在负权回路。2 i( L. c" @) m, \9 I
1 ?" U/ x. s2 T/ b( d' X: B
### 示例代码, U/ ^+ H) \, R5 b( |
4 v. s8 @/ m1 F( Q- p T ```python
0 F; J$ L5 f6 i3 D1 A# C def bellman_ford(graph, start):
0 ^3 X: h/ n/ m1 M( [% @" S # 初始化距离+ e! o2 Y! ~+ E5 m; W4 n5 w
distances = {node: float('inf') for node in graph}% |3 X w8 o3 q- \) F: c
distances[start] = 08 O1 u( Z5 M- ~( x6 Z! e5 y3 _1 W6 V8 [& D
% q/ [8 C7 i5 c* t # 松弛操作% O; p9 q+ A& `& u6 v# \7 A z8 I( H3 O
for _ in range(len(graph) - 1):5 A2 s3 v4 _( Q* }
for u in graph:# V9 j- R+ s1 J2 X. i2 F! r6 C
for v, weight in graph[u].items():, t& c% e3 o) o! a3 l
if distances[u] + weight < distances[v]:
, S5 p6 O) X- H0 U% t; h distances[v] = distances[u] + weight
6 k# U U+ S* V7 ^( b: w / W3 K, A, S+ e/ X4 D% o
# 检查负权回路( r7 D( @% D, d' p
for u in graph:
0 n/ J8 \' _" M l- @3 c for v, weight in graph[u].items():0 @' e s+ ^3 h3 E/ @ ?; ?
if distances[u] + weight < distances[v]:
5 s$ x) ~5 K6 a( Q raise ValueError("Graph contains a negative weight cycle")6 y" i% a' J+ q* W9 q
% ~- u3 \, C) X return distances6 @ f) p9 G" ~
: r# N. m& |7 o. g # 示例图(带有负权边)& B5 y& y4 i6 M/ z% `( v
graph_with_negative_weight = {' S4 r, C5 ]4 m
'A': {'B': 1, 'C': 4},
# I# j* Y" j: q+ v5 V 'B': {'C': -3, 'D': 2},
2 z; T0 u3 y, |2 c* X 'C': {},* I! c" X# B1 {- k& s
'D': {'A': -1}3 A" r# }2 I \0 b! D
}4 f1 m) [* w5 q6 {7 ~
8 o# q$ {5 P! B# G start_node = 'A'
+ r1 t* @0 \* A3 D. x. R/ f shortest_paths = bellman_ford(graph_with_negative_weight, start_node)- J( u: [/ t% R1 p
print(shortest_paths) # {'A': 0, 'B': 1, 'C': -2, 'D': 3}( }. w3 J% V( q6 ^$ P# Y
```
& L4 Z3 N8 s+ z# r 8 Y5 q" M7 q& n* p
## 3. Floyd-Warshall 算法- c9 V" z# ^9 w* u( e8 t$ C3 B$ S5 H
! A4 i! G2 U5 L# E
Floyd-Warshall 算法用于寻找图中所有节点之间的最短路径,适用于边权任意的图,包括有负权边但无负权回路的情况。 K2 r( h( z2 [" B
" t# m. i+ Y6 K! w# {/ k$ {9 ? ### 原理步骤 j6 e9 B- I/ q& p, z; X0 e; a
( X' h# S4 l) i2 O- p8 Z' [ l 1. **初始化**:; H3 }+ t+ t: U& G' v) r# E
- 创建一个距离矩阵,初始化为无穷大,源节点到自身的距离置为0,直接相连的节点的距离为边权。 g7 C+ e8 O, n& ]0 ~4 y( ^
& O# M+ t& @+ w 2. **更新路径**:
8 _: f/ T8 R0 g - 三重循环遍历所有节点,以每个中间节点尝试更新路径。& H4 P0 @- A6 f0 g$ o
5 J% y, Y/ \) I5 S
3. **输出结果**:
8 {1 Q3 O' L/ I% h5 [8 N; c7 z4 t$ t - 最终得到的矩阵即为每对节点之间的最短路径长度。
' N% x( O5 W5 X0 ^7 _
6 w* c! a% n9 U1 [ ### 示例代码+ U9 m) j9 C3 m
, d( Q5 D9 Q% y# t ```python
- T6 E! _) o* G5 f$ e def floyd_warshall(graph):
' y* j6 h2 |6 f/ L/ X # 初始化距离矩阵
* y& o. P/ g: E q nodes = list(graph.keys())
! {" f( @* Z; i" J% c distances = {node: {n: float('inf') for n in nodes} for node in nodes}( E- _; ^- _6 S* p) P
+ P2 E4 E2 g0 X5 Y" G3 d! |- l
for u in nodes:
) P! ^' D& I" ]: j distances[u][u] = 0
! [: [% g7 g! D/ O for v, weight in graph[u].items():1 M4 r2 h" z" u( r
distances[u][v] = weight, q+ \4 J* m2 ~( a: C/ Y1 b; H; d9 }
5 }. X* Z, {7 t5 i& S # 更新路径
- G( l @' u6 d4 J) Z7 C for k in nodes:! R( I- n; L, i
for i in nodes:
( q: V, e7 I% C7 W( _ for j in nodes:
/ F7 I" s E( j if distances[i][j] > distances[i][k] + distances[k][j]:2 G' x# O& M4 P8 K L
distances[i][j] = distances[i][k] + distances[k][j]# e9 _7 F/ t b6 ]& d2 o. O
2 p' W; f6 n% v( a return distances* ?' q* W! s; a8 P0 }. S
% ~' N5 I. l6 _2 _5 R0 o8 j, a
# 示例图(可以含负权边)
# U$ |) h, T5 v2 E6 G/ j; I* J6 o) d graph_for_floyd = {, E" W; y* M0 m" _0 l5 [& E1 w
'A': {'B': 3, 'C': 8, 'D': -4},
4 T7 A3 ]) L# n$ T9 n 'B': {'C': 1, 'D': 7},, v. H1 k8 v4 p6 j" V
'C': {'B': 4},( p" M" {% l; [4 R9 u* i2 A
'D': {'A': 2, 'C': -5}
7 J( | X9 ?1 W% n2 u5 s }
) i1 w. m+ w! b9 H- D/ f8 }& k) _ % R6 J0 M; q2 x5 I
shortest_paths_matrix = floyd_warshall(graph_for_floyd)9 J. Q- }! u6 `1 `, V
for row in shortest_paths_matrix.items():
/ s& Z: ?5 c) O5 r4 p) Y0 W5 v5 Y: J print(row): P- E# y# D. `6 Q7 X
```* q3 d$ A& U9 t; J( C4 A K
: E+ ^' ?1 V: r, H8 \/ ]/ T4 k
## 总结/ n+ W( ?" ~* O- s; v5 |$ C" s
0 k* Q! r9 _* `" e* V - **Dijkstra 算法**适合用于无负权边图,时间复杂度为 \(O((V + E) \log V)\),其中 \(V\) 为节点数,\(E\) 为边数。+ r7 L: t! W3 ? x9 J5 i+ N% _
- **Bellman-Ford 算法**适合处理含负权边的图,时间复杂度为 \(O(VE)\)。
, M: z' b- H) h7 c) e4 B* Y - **Floyd-Warshall 算法**用于所有节点对最短路径计算,时间复杂度为 \(O(V^3)\)。
0 V/ U: \# ?9 Q) S) \3 H
, S6 e- n7 ]( T( C3 C9 V, y+ T7 k 不同算法适用于不同的问题场景,选择适合的算法是解决最短路径问题的关键。如果需要更详细的介绍或有特定问题,欢迎进一步询问!3 J' k; h1 @5 v* j, d
! B3 [5 Q6 P! f5 L* k6 Z
* B( O1 P6 h5 k3 W' @
: g9 k7 t6 i' ~" P" i$ G k
zan