python最短路径优化算法
时间: 2024-01-18 21:18:52 浏览: 26
以下是Python中实现最短路径优化算法的例子:
1. Dijkstra算法:
```python
import heapq
def dijkstra(graph, start):
distances = {node: float('inf') for node in graph}
distances[start] = 0
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': 5, 'C': 2},
'B': {'A': 5, 'C': 1, 'D': 3},
'C': {'A': 2, 'B': 1, 'D': 1},
'D': {'B': 3, 'C': 1, 'E': 4},
'E': {'D': 4}
}
start_node = 'A'
distances = dijkstra(graph, start_node)
print(distances)
```
2. Floyd算法:
```python
def floyd(graph):
n = len(graph)
distances = [[float('inf')] * n for _ in range(n)]
for i in range(n):
for j in range(n):
if i == j:
distances[i][j] = 0
elif j in graph[i]:
distances[i][j] = graph[i][j]
for k in range(n):
for i in range(n):
for j in range(n):
distances[i][j] = min(distances[i][j], distances[i][k] + distances[k][j])
return distances
# 示例图
graph = {
'A': {'B': 5, 'C': 2},
'B': {'A': 5, 'C': 1, 'D': 3},
'C': {'A': 2, 'B': 1, 'D': 1},
'D': {'B': 3, 'C': 1, 'E': 4},
'E': {'D': 4}
}
distances = floyd(graph)
print(distances)
```
3. SPFA算法:
```python
from collections import deque
def spfa(graph, start):
distances = {node: float('inf') for node in graph}
distances[start] = 0
queue = deque([start])
while queue:
current_node = queue.popleft()
for neighbor, weight in graph[current_node].items():
distance = distances[current_node] + weight
if distance < distances[neighbor]:
distances[neighbor] = distance
queue.append(neighbor)
return distances
# 示例图
graph = {
'A': {'B': 5, 'C': 2},
'B': {'A': 5, 'C': 1, 'D': 3},
'C': {'A': 2, 'B': 1, 'D': 1},
'D': {'B': 3, 'C': 1, 'E': 4},
'E': {'D': 4}
}
start_node = 'A'
distances = spfa(graph, start_node)
print(distances)
```