Dijkstra 算法 是什么？

Dijkstra 算法

Dijkstra 算法是一种经典的最短路径算法，用于在图（有向或无向图）中找到从起点到其他所有节点的最短路径。它以广度优先搜索的方式，逐步扩展到目标节点，确保计算出的路径是最短的。

---

1. Dijkstra 算法的基本概念

特点

• 适用于非负权值的图。
• 能够找到从单一源节点到所有其他节点的最短路径。

输入

• 一个图（节点和边）。
• 起始节点（源节点）。

输出

• 从起始节点到其他所有节点的最短路径长度。
• 如果需要，可以记录路径上的具体节点。

---

2. 核心思想

Dijkstra 算法的核心思想是：

• 利用贪心策略，每次选择当前未访问的、距离起点最近的节点进行扩展。
• 一旦访问一个节点，其最短路径就不会被更新（路径确定性）。

---

3. 算法步骤

初始化

1. 创建一个距离表（distance table）：
   • 对每个节点初始化为无穷大（∞），表示当前未知最短路径。
   • 起点的距离设为 0：distance[start] = 0。
2. 创建一个访问表（visited set），记录已访问的节点。
3. 使用一个优先队列或小顶堆（priority queue）存储待访问节点及其距离。

主循环

1. 从优先队列中取出距离起点最近的未访问节点 ( u )。
2. 对 ( u ) 的每个邻居节点 ( v )：
   • 计算从起点通过 ( u ) 到 ( v ) 的路径距离：distance[v] = min(distance[v], distance[u] + weight(u, v))。
   • 如果路径距离更新了，将 ( v ) 加入优先队列。
3. 将 ( u ) 标记为已访问。
4. 重复上述步骤，直到优先队列为空或所有节点的最短路径确定。

路径恢复

如果需要输出路径，可以在更新距离表时记录每个节点的前驱节点，最后从目标节点回溯到起点。

---

4. 伪代码

Dijkstra(Graph, Start):# 初始化distance = {node: ∞ for node in Graph}distance[Start] = 0visited = set()priority_queue = [(0, Start)]  # (distance, node)while priority_queue:# 取出当前距离最小的节点current_distance, current_node = priority_queue.pop()if current_node in visited:continuevisited.add(current_node)# 更新邻居节点的距离for neighbor, weight in Graph[current_node]:new_distance = current_distance + weightif new_distance < distance[neighbor]:distance[neighbor] = new_distancepriority_queue.append((new_distance, neighbor))return distance

---

5. 示例

图示

假设一个加权图如下：

   (A)--1--(B)--4--(D)|       |2       2|       |(C)--1--(E)

输入

• 起点：A
• 图的权值：Graph = {A: [(B, 1), (C, 2)], B: [(A, 1), (D, 4), (E, 2)], C: [(A, 2), (E, 1)], ...}

执行步骤

1. 初始化：distance = {A: 0, B: ∞, C: ∞, D: ∞, E: ∞}。
2. 选择 ( A ) 开始，更新邻居：
   • ( distance[B] = 0 + 1 = 1 )
   • ( distance[C] = 0 + 2 = 2 )
3. 选择 ( B )：
   • ( distance[D] = 1 + 4 = 5 )
   • ( distance[E] = 1 + 2 = 3 )
4. 选择 ( C )：
   • ( distance[E] = min(3, 2 + 1) = 3 )
5. 选择 ( E )、( D )，最终得到：
   • distance = {A: 0, B: 1, C: 2, D: 5, E: 3}。

输出

从 ( A ) 到各节点的最短路径距离：

• ( A \to B: 1 )
• ( A \to C: 2 )
• ( A \to D: 5 )
• ( A \to E: 3 )

---

6. 优缺点

优点

• 高效：适用于稠密图，时间复杂度为 ( O((V + E) \log V) )（使用堆实现）。
• 稳定：保证找到从起点到各节点的最短路径。

缺点

• 限制：不能处理带负权边的图。
• 局限性：只能从一个起点出发计算最短路径，无法同时处理多源问题。

---

7. 应用场景

1. 导航系统：计算最短路径（如 Google Maps）。
2. 网络路由：最优路由规划（如 OSPF 协议）。
3. 游戏开发：角色移动规划。
4. 交通规划：优化物流路径。

---

如果需要更详细的代码示例或具体实现，可以进一步探讨！