Dijkstra算法用于求带权图单源最短路径，核心是贪心策略，每步选最近未处理节点并更新邻居距离。Python常用字典建图、heapq优化，初始化起点距离为0，其余无穷大，用优先队列存（距离, 节点），依次出队最小距离节点，遍历邻居松弛距离，直到队列为空。示例中从A出发得最短路径：{'A': 0, 'B': 1, 'C': 3, 'D': 4}。适用于无向或有向图，要求边权非负，不适用负权边，常见于路由、导航等场景，理解松弛和优先队列是关键。
Dijkstra算法是一种用于求解带权图中单源最短路径的经典算法，由荷兰计算机科学家艾兹赫尔·戴克斯特拉（Edsger W. Dijkstra）在1956年提出。在Python中实现Dijkstra算法，通常是为了找出从一个起始节点到图中其他所有节点的最短路径。
核心思想：贪心策略
Dijkstra算法采用贪心策略，每一步都选择当前距离起点最近且未被处理的节点，然后更新其邻居的距离。这个过程持续进行，直到所有可达节点都被处理完毕。
它适用于有向图或无向图，但要求所有边的权重为非负数（即不能有负权边）。
Python中的常见实现方式
在Python中，通常使用字典表示图，用优先队列（heapq）优化查找最小距离节点的过程，从而提高效率。
立即学习“Python免费学习笔记（深入）”；
基本步骤如下：
- 初始化起点距离为0，其他节点距离为无穷大（float('inf')）
- 使用优先队列存储（距离, 节点）对，按距离从小到大排序
- 每次取出距离最小的节点，遍历其邻居并尝试松弛（relax）距离
- 重复直到队列为空
简单示例代码
import heapq
<p>def dijkstra(graph, start):</p><h1>初始化距离表</h1><pre class='brush:python;toolbar:false;'>distances = {node: float('inf') for node in graph}
distances[start] = 0
# 优先队列：(距离, 节点)
pq = [(0, start)]
while pq:
current_distance, current_node = heapq.heappop(pq)
# 如果已处理过更短路径，跳过
if current_distance > distances[current_node]:
continue
# 检查邻居
for neighbor, weight in graph[current_node].items():
distance = current_distance + weight
# 更新最短距离
if distance < distances[neighbor]:
distances[neighbor] = distance
heapq.heappush(pq, (distance, neighbor))
return distances示例图
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} }
print(dijkstra('A'))
输出: {'A': 0, 'B': 1, 'C': 3, 'D': 4}
适用场景与限制
Dijkstra算法常用于路由算法、地图导航、网络优化等需要计算最短路径的场景。
需要注意的是，如果图中存在负权边，Dijkstra不再适用，应改用Bellman-Ford等算法。
基本上就这些，理解清楚松弛操作和优先队列的作用，就能灵活应用了。
