用list帮我实现dijkstra算法
时间: 2023-10-22 13:08:08 浏览: 43
以下是使用Python实现Dijkstra算法的示例代码:
```python
from queue import PriorityQueue
def dijkstra(graph, start):
# 初始化距离和前驱节点
distance = {node: float('inf') for node in graph}
distance[start] = 0
previous = {node: None for node in graph}
# 按照距离建立优先队列
pq = PriorityQueue()
pq.put((0, start))
# 开始搜索
while not pq.empty():
(dist, current) = pq.get()
# 如果当前节点已经被处理,则跳过
if dist > distance[current]:
continue
# 处理当前节点的邻居
for neighbor, weight in graph[current].items():
new_distance = distance[current] + weight
# 更新距离和前驱节点
if new_distance < distance[neighbor]:
distance[neighbor] = new_distance
previous[neighbor] = current
pq.put((new_distance, neighbor))
return distance, previous
```
其中,`graph`是一个字典,表示无向带权图。字典的键是节点名称,值是一个字典,表示从该节点可以到达的邻居节点及其对应的权重。`start`是算法的起点节点。
例如,以下代码构建了一个简单的无向带权图,并使用Dijkstra算法计算从节点A到其他节点的最短路径:
```python
# 构建无向带权图
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}
}
# 计算最短路径
distance, previous = dijkstra(graph, 'A')
# 输出结果
for node in graph:
path = []
current = node
while current is not None:
path.append(current)
current = previous[current]
path.reverse()
print("Shortest path from A to {}: {}, distance = {}".format(node, path, distance[node]))
```
输出结果为:
```
Shortest path from A to A: ['A'], distance = 0
Shortest path from A to B: ['A', 'B'], distance = 1
Shortest path from A to C: ['A', 'C'], distance = 3
Shortest path from A to D: ['A', 'C', 'D'], distance = 4
```