数学建模社区-数学中国

标题: 最短路径算法Python代码 [打印本页]

作者: 2744557306    时间: 2025-1-13 17:26
标题: 最短路径算法Python代码
最短路径算法用于寻找图中两点之间的最短路径。这类算法在网络路由、地图导航、物流和许多其他应用中起到关键作用。常见的最短路径算法包括 Dijkstra 算法、Bellman-Ford 算法和 Floyd-Warshall 算法。下面将介绍这些算法的基本原理和具体实现。1 {1 N' [4 @* l% u. ^
  [4 |1 x' f' u
## 1. Dijkstra 算法
7 N, v+ X2 g# V0 W7 x- S, D  Y
Dijkstra 算法用于计算单源最短路径,有效于边权为非负数的图。它通过贪心策略逐步选择最短路径,从起点出发扩展到其他节点。
$ C0 {3 ?( x; v* k& _+ t# m. D/ @) x; a2 Q
### 原理步骤
6 y, O2 N# O5 Z' n  R) h7 L
) k1 l% |0 m% M8 d* W1. **初始化**:
5 C' L# ^/ b1 Z6 e   - 设置源节点到自己的距离为0,其他节点为无穷大(一般用 `inf` 表示)。
% z( ], M6 ^1 Z: }4 c# |8 T$ A   - 初始化一个空的优先队列,用于存储待处理的节点。
9 E1 j5 m$ B% D& `- J
2 S5 `4 z" c* C% Z8 H& }, z2. **处理节点**:
: w7 D! |+ U6 c, Y) B   - 从优先队列中选取距离最小的节点作为当前节点。
' U' ?3 f% \3 k4 b6 U   - 更新当前节点的所有邻接节点的距离。如果新的距离更短,则更新并将邻接节点加入优先队列。& n( r2 }% z* |2 M; j) L: H
) K1 T+ ]7 B$ k% |: p
3. **重复处理**:3 w! P: x  c9 S
   - 继续选择距离最小的节点,直到处理完所有节点或找到目标节点。
, {  l/ w+ h7 }+ G# g( j# w; [6 m, |! F( [; j6 R
### 示例代码
) b% x- S$ R! }8 v* R1 g' C2 {- Z+ M& G, [
```python3 |! K8 \" k) M; K& S" x' N' Y
import heapq7 p  K* y! ^8 y1 \. ]+ Q

6 U) ^# o' \: z- Ddef dijkstra(graph, start):
6 n5 s; [4 s  ~) g: p) j, S    # 图的表示为字典,键为节点,值为邻接节点及其边权  L5 ]9 Q6 m" T) [% J
    queue = []5 I2 h  W7 Q+ ?4 P
    distances = {node: float('inf') for node in graph}
6 y4 X9 m  v) i  @1 Z, q    distances[start] = 0: @! z7 B' O5 G- b' S
    heapq.heappush(queue, (0, start))  # (距离, 节点)
0 P- X  z( B' ^5 L9 ?/ k
7 S: F  h, b/ e8 [* Y    while queue:
3 S* [" ^% N. z" o! N& N        current_distance, current_node = heapq.heappop(queue)- M- V: n3 X0 @, X: U. z; H

4 O' z% J) A, c1 d# l        # 只处理当前节点的最短距离
6 B: K3 j# p* s7 Q/ m% O( Q& N+ {, O        if current_distance > distances[current_node]:0 ~. f+ e2 U( x3 v
            continue
) _- `6 W  H/ q5 b5 U+ l9 V( H: r/ [# J7 c) }
        for neighbor, weight in graph[current_node].items():2 j! T; Q/ g7 j% {5 r. M4 h6 D
            distance = current_distance + weight9 n+ t6 l. V, S' M- a3 G

$ @# d$ G0 Z& e( ~            # 更新邻接节点的距离
5 q5 ?' o0 k& F8 q9 E' d0 ^            if distance < distances[neighbor]:
+ U/ @3 ^, n: c( y                distances[neighbor] = distance
' l# I4 J, x% \" v- Z3 `                heapq.heappush(queue, (distance, neighbor))
9 S" B  @8 b0 `* S- H% F
2 I/ ~( V& y* n. N" e0 D    return distances
& g5 U: H; B8 U7 z7 P3 ]0 u" V' a8 r' W1 s+ M5 d0 i2 L
# 示例图: f; H6 X) U, z7 I2 E
graph = {
4 U/ G7 s6 ]7 k& I0 e3 D    'A': {'B': 1, 'C': 4},3 O( q  q% D7 h5 x. y5 k5 ~% I  R
    'B': {'A': 1, 'C': 2, 'D': 5},
+ @( ^, d  ~+ a( a0 @9 Y, B% n1 ^, P2 z    'C': {'A': 4, 'B': 2, 'D': 1},  H! n2 t6 M% ]- ?0 g
    'D': {'B': 5, 'C': 1},: n4 D+ m8 \$ r. a  R8 d
}$ X- G7 I* X; K7 u
- y# f5 M( z5 G4 W, F- y
start_node = 'A'
5 L$ Q( {% V% c  m0 h# tshortest_paths = dijkstra(graph, start_node)
, Q: Q" H, @* Y( u, {print(shortest_paths)  # {'A': 0, 'B': 1, 'C': 3, 'D': 4}# k& S3 H: n$ h/ C5 T. \: [8 Y
```
+ {; x9 o& D& [: |
+ N+ p  S6 j9 v8 W# J## 2. Bellman-Ford 算法, U7 L; k1 c. a5 _% y1 x
; G1 Y8 }- {% M- c/ i
Bellman-Ford 算法能够处理带有负权边的图,但不能处理负权回路。它通过放松操作逐步更新从源节点到所有其他节点的最短路径。
1 K: @4 f- Y1 y) d, Q" J
" M  A6 n- g$ Z% V### 原理步骤
$ O' f! p5 E* @' O( x- j6 i
9 F! d& q% C% f% I# ~* v1. **初始化**:
" e  b7 |5 @3 v' f5 i1 i1 V' {& g   - 设置源节点到自己的距离为0,其他节点为无穷大。1 |( U2 o" L! x! f4 ]" U3 j
0 w* n( P0 Y) |  J' |3 w
2. **松弛操作**:
' X" v+ v! w2 t. R& B& d2 c* ]+ @   - 对所有边进行松弛操作,循环(V-1)次(V为节点数),尝试更新每个边的距离。7 H5 m& o5 f- N  X) s3 }- e" l
4 p  c4 K2 a) ~4 Q3 D; [1 ^9 ?
3. **检查负权回路**:
& Q: f/ d! ^; r+ @+ ?: L   - 再次对所有边进行一次松弛检查,如果有边的距离仍能被更新,则说明图中存在负权回路。3 m  ~( R: W4 i6 m& i
) g+ G) M+ K: `0 r" f. S
### 示例代码
; p# G9 ?5 U, l( b4 U
! ^$ M7 O9 l( L5 _: w# ?7 n' R: }& U```python
7 o# f, @, y* M0 d& [3 _% Gdef bellman_ford(graph, start):- b% e1 V" B) ]& L
    # 初始化距离# X3 `2 t: B. q2 ], ?5 U
    distances = {node: float('inf') for node in graph}
5 w2 \! o& ^+ _* N& h    distances[start] = 0
' w& d* S  m) w! i! G; o  n/ B8 v; L8 k' x( u9 u: V1 z. _
    # 松弛操作
& n& H* U; o! p/ g/ J5 B7 Y    for _ in range(len(graph) - 1):
; O4 a/ i/ M0 B        for u in graph:3 R0 h- A8 j/ v$ G+ ^: X
            for v, weight in graph[u].items():
; V/ Z1 q2 s! c' o7 ^: J                if distances[u] + weight < distances[v]:
3 ^9 L: b  h# Z. g6 V  o6 O                    distances[v] = distances[u] + weight! k+ h& i: d9 B* C+ B
4 b! R* `; k& q. P
    # 检查负权回路% D7 B/ q# o2 E5 F8 q" q
    for u in graph:/ Q# F* Z1 K3 j2 ]7 j9 `+ R
        for v, weight in graph[u].items():
3 k2 l& `8 g# E            if distances[u] + weight < distances[v]:
' t% q/ ]6 W, \5 m1 _# f                raise ValueError("Graph contains a negative weight cycle")
. @/ w6 q) A' o& R! _& Q! B
) Q! b. U! u% l4 ~- q3 l    return distances
  {" Q" b9 ~( P: w# b9 V  V7 x) d
( t$ t  q  `6 U7 E+ W  U' O5 b5 h# 示例图(带有负权边)
. J, |5 N! z0 c/ vgraph_with_negative_weight = {
' J5 ?! n( {) U$ H4 N+ q    'A': {'B': 1, 'C': 4},) R4 h1 J) @0 i8 {# E" f* v" Y8 C# r
    'B': {'C': -3, 'D': 2},
/ ^5 u6 o* w. ?    'C': {},- A+ h, B' u; t% F4 b
    'D': {'A': -1}
2 G* v- S- z/ n. x}4 F7 ~& j" ]& j0 _; N

+ y9 v6 G; q( k2 Nstart_node = 'A'
8 @3 G6 o% N/ N* ushortest_paths = bellman_ford(graph_with_negative_weight, start_node)
$ d/ Y  W" @  E3 n. ~/ T* z% Eprint(shortest_paths)  # {'A': 0, 'B': 1, 'C': -2, 'D': 3}# q  d. \/ f7 w* s& H& }( A( y
```9 c% L4 R# C( C! z7 g

  ~# A& s7 p, e& v. L# S. s## 3. Floyd-Warshall 算法
6 S4 y+ ]( n" X) m, {* j2 b& Z: \) C/ B
Floyd-Warshall 算法用于寻找图中所有节点之间的最短路径,适用于边权任意的图,包括有负权边但无负权回路的情况。7 @' L! t0 g& y' z* b( ~
9 {3 T5 O, S- W2 W6 g
### 原理步骤& Z$ c5 ]. t$ y1 N' s
7 ?: Z+ i3 Q( }5 o
1. **初始化**:
+ X/ Q. U( O' A9 L# e3 k   - 创建一个距离矩阵,初始化为无穷大,源节点到自身的距离置为0,直接相连的节点的距离为边权。
1 g9 j9 |5 F$ \
" y! C9 c/ C+ `% N$ }+ R0 U- `2. **更新路径**:
' B+ M1 U0 o0 ?2 s& G8 w   - 三重循环遍历所有节点,以每个中间节点尝试更新路径。( o4 J# A/ B" R6 P6 N& L' U
8 {* d7 C9 g$ `; I+ v' |
3. **输出结果**:* J$ m) }9 V& _1 s: c# J
   - 最终得到的矩阵即为每对节点之间的最短路径长度。, j, u  S5 J/ E  ^; b
/ h2 [4 o9 O4 J/ f/ C6 B, v
### 示例代码$ P3 B. c: H$ O& ^
( V$ x& Q+ g- V3 Z! H4 m+ A; o; N
```python
* s7 T  m  K3 f! @! vdef floyd_warshall(graph):
9 X6 o" ~1 [0 Y3 m6 L    # 初始化距离矩阵
% r4 f2 J5 i- n7 \% |* m    nodes = list(graph.keys())
+ |% F9 d, |' G  D/ E" F7 A7 c3 [    distances = {node: {n: float('inf') for n in nodes} for node in nodes}4 |" a: Q3 |: l. A/ N/ y
4 Q; M8 J; x. v2 ?( ?9 D
    for u in nodes:
* h. e8 J, _. w$ e, K/ N        distances[u][u] = 0
0 |0 n  K) m6 N& T        for v, weight in graph[u].items():
% b4 {: p$ m7 c- ]% v: U            distances[u][v] = weight0 N3 Y/ j1 A1 P/ I% z
; u; P9 X" T8 \, G
    # 更新路径1 V- G4 v8 r. r  c$ y
    for k in nodes:
9 ^) d* }3 w. P! I7 N/ ]        for i in nodes:
+ g2 j: i7 ]% G6 D; Q" H6 P. z8 T            for j in nodes:
! z% G. n, L3 V( X                if distances[i][j] > distances[i][k] + distances[k][j]:
% `, U+ h6 @" c. d1 Q  r- a                    distances[i][j] = distances[i][k] + distances[k][j]
3 C) G" v8 b2 v2 x6 r7 g" j* L
    return distances
, Y% U/ ?& T0 ^; @
+ r- L1 V4 l4 ~- j  f  W6 {. |# 示例图(可以含负权边)
5 F. P/ @$ u" `( Agraph_for_floyd = {9 e+ {5 c6 w, L2 w2 X$ g
    'A': {'B': 3, 'C': 8, 'D': -4},
# l/ z% }: |: w1 h    'B': {'C': 1, 'D': 7},) d; I7 w% x( p8 q' h; _5 I+ V
    'C': {'B': 4},7 p7 X7 a; m7 I- I1 D3 z
    'D': {'A': 2, 'C': -5}
5 Q: i/ l% a" P- y$ H}
' g/ O. K: H9 j! Y- x0 ?9 o8 C- F( o, e1 k. H
shortest_paths_matrix = floyd_warshall(graph_for_floyd)  w: F+ m9 i& w; L9 o1 A
for row in shortest_paths_matrix.items():& q- p0 ]* ]* F
    print(row)6 b( R# a! k, Q5 e
```
/ N' p# a  _7 Z8 T
6 y: i# z4 @: u## 总结/ m1 O. J5 \8 y( W6 {  N
* Y! m% Y& w" ^( G% \% y% D4 `  X
- **Dijkstra 算法**适合用于无负权边图,时间复杂度为 \(O((V + E) \log V)\),其中 \(V\) 为节点数,\(E\) 为边数。9 Z1 s/ B; @" t' g7 A
- **Bellman-Ford 算法**适合处理含负权边的图,时间复杂度为 \(O(VE)\)。
1 k/ z1 \+ m- v: F6 \0 L) e. R" r- **Floyd-Warshall 算法**用于所有节点对最短路径计算,时间复杂度为 \(O(V^3)\)。
; e; `) t2 [' i; o5 ]+ D6 W2 l$ z) S: V" G$ }$ L6 N
不同算法适用于不同的问题场景,选择适合的算法是解决最短路径问题的关键。如果需要更详细的介绍或有特定问题,欢迎进一步询问!3 f; @' z0 k* x- s& y1 m

. I' k. R5 J8 w( ?6 ]! K- O' P! q5 f( y- I5 ~# G

) m$ O: C, k% K4 m. D# q: ]

最短路径算法Python代码.docx

13.29 KB, 下载次数: 0, 下载积分: 体力 -2 点

售价: 2 点体力  [记录]  [购买]






欢迎光临 数学建模社区-数学中国 (http://www.madio.net/) Powered by Discuz! X2.5