查看: 2450|回复: 0

最短路径算法Python代码

字体大小: 正常放大

1189 主题	4 听众	2934 积分

该用户从未签到

电梯直达

1^#

发表于 2025-1-13 17:26 |只看该作者 |倒序浏览

|招呼Ta 关注Ta

最短路径算法用于寻找图中两点之间的最短路径。这类算法在网络路由、地图导航、物流和许多其他应用中起到关键作用。常见的最短路径算法包括 Dijkstra 算法、Bellman-Ford 算法和 Floyd-Warshall 算法。下面将介绍这些算法的基本原理和具体实现。

## 1. Dijkstra 算法

Dijkstra 算法用于计算单源最短路径，有效于边权为非负数的图。它通过贪心策略逐步选择最短路径，从起点出发扩展到其他节点。

### 原理步骤

1. **初始化**：
- 设置源节点到自己的距离为0，其他节点为无穷大（一般用 `inf` 表示）。
- 初始化一个空的优先队列，用于存储待处理的节点。

2. **处理节点**：
- 从优先队列中选取距离最小的节点作为当前节点。
- 更新当前节点的所有邻接节点的距离。如果新的距离更短，则更新并将邻接节点加入优先队列。

3. **重复处理**：
- 继续选择距离最小的节点，直到处理完所有节点或找到目标节点。

### 示例代码

```python
import heapq

def dijkstra(graph, start):
# 图的表示为字典，键为节点，值为邻接节点及其边权
queue = []
distances = {node: float('inf') for node in graph}
distances[start] = 0
heapq.heappush(queue, (0, start))  # (距离, 节点)

while queue:
      current_distance, current_node = heapq.heappop(queue)

      # 只处理当前节点的最短距离
      if current_distance > distances[current_node]:
         continue

      for neighbor, weight in graph[current_node].items():
         distance = current_distance + weight

         # 更新邻接节点的距离
         if distance < distances[neighbor]:
            distances[neighbor] = distance
            heapq.heappush(queue, (distance, neighbor))

return distances

# 示例图
graph = {
'A': {'B': 1, 'C': 4},
'B': {'A': 1, 'C': 2, 'D': 5},
'C': {'A': 4, 'B': 2, 'D': 1},
'D': {'B': 5, 'C': 1},
}

start_node = 'A'
shortest_paths = dijkstra(graph, start_node)
print(shortest_paths)  # {'A': 0, 'B': 1, 'C': 3, 'D': 4}
```

## 2. Bellman-Ford 算法

Bellman-Ford 算法能够处理带有负权边的图，但不能处理负权回路。它通过放松操作逐步更新从源节点到所有其他节点的最短路径。

### 原理步骤

1. **初始化**：
- 设置源节点到自己的距离为0，其他节点为无穷大。

2. **松弛操作**：
- 对所有边进行松弛操作，循环(V-1)次（V为节点数），尝试更新每个边的距离。

3. **检查负权回路**：
- 再次对所有边进行一次松弛检查，如果有边的距离仍能被更新，则说明图中存在负权回路。

### 示例代码

```python
def bellman_ford(graph, start):
# 初始化距离
distances = {node: float('inf') for node in graph}
distances[start] = 0

# 松弛操作
for _ in range(len(graph) - 1):
      for u in graph:
         for v, weight in graph[u].items():
            if distances[u] + weight < distances[v]:
                  distances[v] = distances[u] + weight

# 检查负权回路
for u in graph:
      for v, weight in graph[u].items():
         if distances[u] + weight < distances[v]:
            raise ValueError("Graph contains a negative weight cycle")

return distances

# 示例图（带有负权边）
graph_with_negative_weight = {
'A': {'B': 1, 'C': 4},
'B': {'C': -3, 'D': 2},
'C': {},
'D': {'A': -1}
}

start_node = 'A'
shortest_paths = bellman_ford(graph_with_negative_weight, start_node)
print(shortest_paths)  # {'A': 0, 'B': 1, 'C': -2, 'D': 3}
```

## 3. Floyd-Warshall 算法

Floyd-Warshall 算法用于寻找图中所有节点之间的最短路径，适用于边权任意的图，包括有负权边但无负权回路的情况。

### 原理步骤

1. **初始化**：
- 创建一个距离矩阵，初始化为无穷大，源节点到自身的距离置为0，直接相连的节点的距离为边权。

2. **更新路径**：
- 三重循环遍历所有节点，以每个中间节点尝试更新路径。

3. **输出结果**：
- 最终得到的矩阵即为每对节点之间的最短路径长度。

### 示例代码

```python
def floyd_warshall(graph):
# 初始化距离矩阵
nodes = list(graph.keys())
distances = {node: {n: float('inf') for n in nodes} for node in nodes}

for u in nodes:
      distances[u][u] = 0
      for v, weight in graph[u].items():
         distances[u][v] = weight

# 更新路径
for k in nodes:
      for i in nodes:
         for j in nodes:
            if distances[i][j] > distances[i][k] + distances[k][j]:
                  distances[i][j] = distances[i][k] + distances[k][j]

return distances

# 示例图（可以含负权边）
graph_for_floyd = {
'A': {'B': 3, 'C': 8, 'D': -4},
'B': {'C': 1, 'D': 7},
'C': {'B': 4},
'D': {'A': 2, 'C': -5}
}

shortest_paths_matrix = floyd_warshall(graph_for_floyd)
for row in shortest_paths_matrix.items():
print(row)
```

## 总结

- **Dijkstra 算法**适合用于无负权边图，时间复杂度为 \(O((V + E) \log V)\)，其中 \(V\) 为节点数，\(E\) 为边数。
- **Bellman-Ford 算法**适合处理含负权边的图，时间复杂度为 \(O(VE)\)。
- **Floyd-Warshall 算法**用于所有节点对最短路径计算，时间复杂度为 \(O(V^3)\)。

不同算法适用于不同的问题场景，选择适合的算法是解决最短路径问题的关键。如果需要更详细的介绍或有特定问题，欢迎进一步询问！