dijkstra算法代码
时间：2026-10-31 11:38:04来源：Dijkstra算法是一种用于求解单源最短路径问题的经典算法，适用于边权为非负的图。以下是该算法的核心步骤与实现方式总结：
| 步骤 | 说明 |
| 1 | 初始化距离数组，起点距离为0，其余为无穷大 |
| 2 | 使用优先队列（或最小堆）存储待处理节点 |
| 3 | 取出当前距离最小的节点，更新其邻接节点的距离 |
| 4 | 重复步骤3，直到所有节点处理完毕或目标节点被找到 |
以下是简单实现代码示例（Python）：
```python
import heapq
def dijkstra(graph, start):
dist = {node: float( inf ) for node in graph}
dist[start] = 0
heap = [(0, start)
while heap:
current_dist, current_node = heapq.heappop(heap)
if current_dist > dist[current_node]:
continue
for neighbor, weight in graph[current_node].items():
new_dist = current_dist + weight
if new_dist < dist[neighbor]:
dist[neighbor] = new_dist
heapq.heappush(heap, (new_dist, neighbor))
return dist
```
该算法时间复杂度为 O(E log V)，适用于大多数实际应用场景。
展开更多
标签：
