数学建模社区-数学中国

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

作者: 2744557306    时间: 2025-1-13 17:26
标题: 最短路径算法Python代码
最短路径算法用于寻找图中两点之间的最短路径。这类算法在网络路由、地图导航、物流和许多其他应用中起到关键作用。常见的最短路径算法包括 Dijkstra 算法、Bellman-Ford 算法和 Floyd-Warshall 算法。下面将介绍这些算法的基本原理和具体实现。
) u$ e: D) ~% l( D" D* \8 F: V6 i8 n2 @% J0 Q% N! L3 P: w
## 1. Dijkstra 算法
: A" Q3 K) w2 _$ h  B1 r
4 v  X+ _' k" x+ d5 g6 t' c4 lDijkstra 算法用于计算单源最短路径,有效于边权为非负数的图。它通过贪心策略逐步选择最短路径,从起点出发扩展到其他节点。
2 A! V/ u) h9 b, m; M; a
% `; w! l: l* V6 B### 原理步骤
: A  p3 N0 J  k* x" R7 v4 }$ z3 Z7 D
1. **初始化**:9 u$ i9 }( l( C. M8 l2 ^, R. v! |" K, }  `
   - 设置源节点到自己的距离为0,其他节点为无穷大(一般用 `inf` 表示)。
# ?" M$ }% _5 ?% h. j7 b   - 初始化一个空的优先队列,用于存储待处理的节点。
$ p% p+ _. t' e+ E5 |, k
: G: ~0 U% Z7 G1 A8 Y2. **处理节点**:; y7 p$ Q2 J% l: j( @2 a5 ^
   - 从优先队列中选取距离最小的节点作为当前节点。
7 y& t- @/ |# s/ T  |* I4 y   - 更新当前节点的所有邻接节点的距离。如果新的距离更短,则更新并将邻接节点加入优先队列。6 {0 Q6 i/ }& T8 A( G

4 d! f+ p: D4 o. C3. **重复处理**:
2 w. p* T0 E; X/ U- x1 I" L   - 继续选择距离最小的节点,直到处理完所有节点或找到目标节点。
' C* [3 O$ P5 j* J  T4 [( i& b  j1 L; @
### 示例代码
" a- j$ ]) q! I( P5 t: h0 I5 a. k! e$ \1 W5 O" m5 U# ?. K
```python
: [+ T& d0 ^+ R& g  Y! X$ e9 }! mimport heapq
5 ?% i6 J3 Z5 c; n' L$ H! B7 k+ V
. T- r, G- l5 f2 qdef dijkstra(graph, start):
$ W9 N  W, X7 G7 x, C+ K    # 图的表示为字典,键为节点,值为邻接节点及其边权! F7 |5 p: L- j  R& O: v& o4 |
    queue = []3 s) c7 Q7 N4 r
    distances = {node: float('inf') for node in graph}2 V* _- i% M4 E. C  _
    distances[start] = 0
1 b  {$ C; L$ O) {+ h    heapq.heappush(queue, (0, start))  # (距离, 节点)
% P; k+ v2 l7 E/ m. M. T# @+ R( \: H. A. {( t! l
    while queue:9 ?; E+ }: l2 U! a7 z& M2 ^& a
        current_distance, current_node = heapq.heappop(queue): z$ w9 Z' K" S: h+ q1 l5 D- K! D

) s6 r) a  t. J, F) t5 ?        # 只处理当前节点的最短距离
0 x8 k9 I7 ]& O' f0 [1 j: j9 G. ~/ W        if current_distance > distances[current_node]:4 p) z; d& g  d& m' ~9 j# b
            continue
# ?5 p* n0 b" W- m3 w4 o( q0 [! ]  P9 ^+ O1 Y+ H" g
        for neighbor, weight in graph[current_node].items():9 N% [' N* v9 P
            distance = current_distance + weight
2 F) `1 I. @! v- h4 e$ ~/ w1 {! b: q
            # 更新邻接节点的距离
& P" T  c% ]& H, ^0 _$ c            if distance < distances[neighbor]:: ^# e+ V/ q2 ~: i
                distances[neighbor] = distance! U- P% E* |3 w2 w6 r
                heapq.heappush(queue, (distance, neighbor))
9 g9 @& ?% v& ]; ~% W+ G7 a& Y. W  b; A' w4 b& c5 T0 `
    return distances: ?1 j% |. H! T% |* t; I' U* B

" ]5 k& D2 j* J: s# 示例图& j8 b8 t, u% l8 m  c1 r6 w
graph = {
) w* z2 c3 j0 V& O    'A': {'B': 1, 'C': 4},
1 J/ ?( G# S6 C( j6 w8 F    'B': {'A': 1, 'C': 2, 'D': 5},7 B$ J4 V) `. u  Z& C
    'C': {'A': 4, 'B': 2, 'D': 1},
* I* e7 C* f4 L* t* S: h1 j# r    'D': {'B': 5, 'C': 1},% F4 [, S7 y- @$ }5 ~. }% R
}
, E4 ?) {) e9 V) w9 s0 @6 \+ e4 {0 X' s3 T7 N) o
start_node = 'A'8 a" ?' [9 R/ s$ O/ A
shortest_paths = dijkstra(graph, start_node)
% X+ x3 q  Z1 f+ d/ Kprint(shortest_paths)  # {'A': 0, 'B': 1, 'C': 3, 'D': 4}" n) w4 c+ l$ x4 d
```
% n0 S# B1 K6 [  N" }7 I. H: J" v' h
## 2. Bellman-Ford 算法% ]. b: x9 x3 l* q

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

: ^, T9 {2 `# S' O7 V' d# ^start_node = 'A', _  F) y7 \" i' m7 W, y1 Z0 R
shortest_paths = bellman_ford(graph_with_negative_weight, start_node)
+ Z; @* S6 ^$ c2 |print(shortest_paths)  # {'A': 0, 'B': 1, 'C': -2, 'D': 3}8 i) }" o9 ~+ R5 e( [- h
```- {( a8 ^% x5 s' O( Z' }

7 c! g( {$ [  f% P## 3. Floyd-Warshall 算法5 p$ h- g1 `& m# W5 `
6 ?; q8 z/ B9 T/ l' h0 x
Floyd-Warshall 算法用于寻找图中所有节点之间的最短路径,适用于边权任意的图,包括有负权边但无负权回路的情况。+ C+ U9 q* I0 f4 U' o4 `4 A
: f. W& s! K: c  \! t, B/ K
### 原理步骤& O' J1 ~& T; W$ o  l$ O0 d

: d) [. G  e3 ~3 v% l4 X1. **初始化**:' P: ]: ^3 o; f) B; `! w. G4 F
   - 创建一个距离矩阵,初始化为无穷大,源节点到自身的距离置为0,直接相连的节点的距离为边权。
. o9 }2 R7 q# y' v( H9 }
) x4 o! {+ K2 v1 x" S2. **更新路径**:
0 q  f3 S: D% ^; A' r$ m   - 三重循环遍历所有节点,以每个中间节点尝试更新路径。
) p( o1 Q9 f5 ^/ K# @5 I; }
' a; o. L; E( l$ A& g. ?( j! ~1 e3. **输出结果**:
- X2 e: P/ K- Z9 u" l# @% ?6 Y( d   - 最终得到的矩阵即为每对节点之间的最短路径长度。+ K  m) j% Y6 v' F1 o0 `) C0 A! X

( |; ^4 i. x* M7 d% Z  B1 A  g### 示例代码4 t+ ]0 M. q% J: [* o/ s

  u/ ~! u+ _1 A4 x( S( F& t3 j4 c```python4 A- I8 ?% p5 p+ v0 w
def floyd_warshall(graph):
8 j( l+ R% K# e$ g: b; U    # 初始化距离矩阵9 z3 P7 @6 f/ f! Y
    nodes = list(graph.keys()), ^! W: u* }6 h1 J6 r  k7 q
    distances = {node: {n: float('inf') for n in nodes} for node in nodes}
, M5 z  k; Z; l7 s2 T) K. D/ e
/ f* U+ a4 p- K" ~  M+ Y. W. ~    for u in nodes:/ Y1 o& U2 N  p1 T
        distances[u][u] = 0
0 @' ]8 I8 z; T' e. |        for v, weight in graph[u].items():
. n/ h5 ]  ~9 g6 J6 [  Y            distances[u][v] = weight, a0 p) ^: g7 ]9 Y8 r/ i* P
- T8 \; y$ p6 |9 q* \( o
    # 更新路径" Q. {8 [1 }- c1 `( w, `+ ^
    for k in nodes:
, P4 y% w. f) n/ n5 q0 K        for i in nodes:
4 i3 E# C6 V: s: b% y# E- b5 X            for j in nodes:
" j8 a6 x. D8 F" C' _% I                if distances[i][j] > distances[i][k] + distances[k][j]:
3 |. i1 S9 ?6 S% b2 G                    distances[i][j] = distances[i][k] + distances[k][j]0 M+ B+ T  _9 ~( K" k( q
4 ^3 p" s1 M3 D1 F
    return distances4 o% |* z1 {9 q% j. O: ~
) m" q/ V0 J+ L; X6 X- Z0 J
# 示例图(可以含负权边)
$ O3 p$ L* X& Ugraph_for_floyd = {
9 c- x: P' l: _% b6 V    'A': {'B': 3, 'C': 8, 'D': -4},
" |$ N& @, T% l+ E3 t. @    'B': {'C': 1, 'D': 7},
$ G& o) C0 x% f$ ~; D- e+ d    'C': {'B': 4},2 @. `" R. B5 g' d( a8 K9 w
    'D': {'A': 2, 'C': -5}' m9 q4 e0 [5 \# t% C( ~/ w7 ~  \4 u' M1 {
}
# h% G0 |3 _+ x3 O5 c; E7 E: F7 y3 A( K0 L1 z' x1 |
shortest_paths_matrix = floyd_warshall(graph_for_floyd)
( g% t% Q) F, t  nfor row in shortest_paths_matrix.items():6 r6 ]1 R, W  O. `" l
    print(row)
) H; c+ g" U+ N$ M& N, b0 i& p```
+ j6 _  \+ E' {# j* w, U. ?0 T* |1 O' q& P9 z  ~- o
## 总结
7 b7 h0 r! g1 Z( U8 O2 ~$ @1 h) C: Z; M0 ?9 c, V1 ~7 e/ Z
- **Dijkstra 算法**适合用于无负权边图,时间复杂度为 \(O((V + E) \log V)\),其中 \(V\) 为节点数,\(E\) 为边数。
# u' ?. \0 z" D" j6 N+ I- **Bellman-Ford 算法**适合处理含负权边的图,时间复杂度为 \(O(VE)\)。9 i  j% a( |: A" ^
- **Floyd-Warshall 算法**用于所有节点对最短路径计算,时间复杂度为 \(O(V^3)\)。
- a6 C4 A0 M$ n7 E3 f2 L1 g! Q' ?4 i) l6 p/ i& L8 m( M
不同算法适用于不同的问题场景,选择适合的算法是解决最短路径问题的关键。如果需要更详细的介绍或有特定问题,欢迎进一步询问!
/ M, l, R  v4 Y0 ~& b1 Q. D& z; I+ C  G8 p) }
- T5 J* B  R6 {, ]

  o, |3 z1 ~4 ]; ]( P3 f" V6 w1 b

最短路径算法Python代码.docx

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

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






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