dijkstra算法求最短路径python
时间: 2023-04-26 15:06:08 浏览: 69
Dijkstra算法是一种用于求解带权有向图中单源最短路径的算法。它的基本思想是从起点开始,逐步扩展到所有节点,每次选择当前距离起点最近的一个节点进行扩展,直到扩展到终点或者所有节点都被扩展完毕。
在Python中,可以使用以下代码实现Dijkstra算法:
```python
import heapq
def dijkstra(graph, start):
# 初始化距离和前驱节点
dist = {node: float('inf') for node in graph}
dist[start] =
prev = {node: None for node in graph}
# 使用堆来存储未处理的节点
heap = [(, start)]
while heap:
# 取出距离起点最近的节点
(d, node) = heapq.heappop(heap)
# 如果该节点已经处理过,则跳过
if d > dist[node]:
continue
# 遍历该节点的所有邻居节点
for neighbor in graph[node]:
# 计算到该邻居节点的距离
distance = dist[node] + graph[node][neighbor]
# 如果该距离比已知的距离更短,则更新距离和前驱节点
if distance < dist[neighbor]:
dist[neighbor] = distance
prev[neighbor] = node
# 将该邻居节点加入堆中
heapq.heappush(heap, (distance, neighbor))
# 返回最短路径和距离
path = []
node = end
while node is not None:
path.append(node)
node = prev[node]
path.reverse()
return path, dist[end]
```
其中,graph是一个字典,表示带权有向图,每个节点对应一个字典,存储该节点的邻居节点和对应的边权值。start表示起点,end表示终点。函数返回最短路径和距离。