写一个python语言实现的最短路径算法
时间: 2023-05-31 21:04:14 浏览: 45
以下是Dijkstra算法的Python实现:
```python
import heapq
def dijkstra(graph, start):
dist = {node: float('inf') for node in graph}
dist[start] = 0
pq = [(0, start)]
while pq:
(cost, current_node) = heapq.heappop(pq)
if cost > dist[current_node]:
continue
for neighbor, weight in graph[current_node].items():
new_cost = dist[current_node] + weight
if new_cost < dist[neighbor]:
dist[neighbor] = new_cost
heapq.heappush(pq, (new_cost, neighbor))
return dist
```
其中,graph是一个字典,表示节点之间的连接关系和权重。例如,如果有两个节点A和B之间的距离是5,则graph可以表示为:
```
graph = {
'A': {'B': 5},
'B': {'A': 5}
}
```
start是起始节点的名称。该算法返回一个字典,表示从起始节点到每个节点的最短距离。