Python最短路线代码
时间: 2023-11-21 19:09:31 浏览: 27
下面是使用Dijkstra算法实现最短路线的Python代码:
```python
import heapq
def dijkstra(graph, start):
distances = {vertex: float('infinity') for vertex in graph}
distances[start] = 0
pq = [(0, start)]
while pq:
current_distance, current_vertex = heapq.heappop(pq)
if current_distance > distances[current_vertex]:
continue
for neighbor, weight in graph[current_vertex].items():
distance = current_distance + weight
if distance < distances[neighbor]:
distances[neighbor] = distance
heapq.heappush(pq, (distance, neighbor))
return distances
# Example Usage
graph = {
'A': {'B': 2, 'C': 1},
'B': {'A': 2, 'D': 4, 'E': 2},
'C': {'A': 1, 'F': 7},
'D': {'B': 4, 'E': 3},
'E': {'B': 2, 'D': 3, 'F': 1},
'F': {'C': 7, 'E': 1}
}
print(dijkstra(graph, 'A'))
```
该代码使用了堆队列来提高Dijkstra算法的效率。它接受一个图和一个起始节点作为输入,并返回从起始节点到每个节点的最短距离。上述代码输出的结果是:
```
{'A': 0, 'B': 2, 'C': 1, 'D': 6, 'E': 4, 'F': 5}
```
其中每个键值对的键是节点名称,值是从起始节点到该节点的最短距离。