23. Shortest Paths

Shortest Paths Tree（SPT）

最短路径树即从源点到所有节点的最短路径，组合起来形成的一棵树

假设从 G 开始，有 V 个节点。
假设每个顶点都是可到达的，则 G 的最短路径树的边永远是 V - 1 个

Dijkstra’s Algorithm

Dijkstra 通常要求边权非负。

核心步骤：

• 每个节点维护两个变量：
  • distTo：从源点到当前节点的最短距离，初始为 ∞（源点自身为 0）
  • edgeTo：当前最短路径中，该节点是从哪个节点到达的
• 还需要一个 Priority Queue：
  • 包含待处理节点，按 distTo 的大小维护
• 从源点出发，
  1. 从优先队列中取出 distTo 最小的节点作为当前节点
  2. 检查当前节点的所有邻居，对邻居进行 “relax” 操作，即试图去更新源点和邻居的最短距离：
     • 新距离 = 当前节点的 distTo + 边的权重
     • 如果 新距离 < 邻居原本的 distTo：
       • 将 distTo 更新为新距离
       • 将 edgeTo 更新
       • 将该邻居加入 PQ
  3. 重复上述步骤，直到 PQ 为空

演示幻灯片

• 例：上图展示了一个更新 4 节点的操作
  • 从 4 沿着路径出发，检查它能够到达的所有邻居
    • 计算新距离（ 4 的 distTo 是 5，再加上边的权重）
      • 4 -> 5：原 distTo 为 16，现在是 9，则更新为 9
      • 4 -> 6：原 distTo 为无限，现在是 10，则更新为 10
    • 将 5 和 6 加入 PQ
  • 下一步，更新 5 ，因为它的 distTo 最小

A* 算法

A* 和 Dijkstra 实现的异同之处：

1. PQ 将不再根据 distTo 的大小维护，而是根据 distTo + h(v, goal) 维护
2. 每个节点多维护一个 h(v,goal) 变量
3. 其余都延续 Dijkstra 算法

核心思想：不只考虑“从起点到当前节点已经走了多远”，还考虑“从当前节点到终点大概还剩多远”

h(v, goal)的含义：

• 这是一个“启发式估计”，它不是实际的距离，就是一个估计距离，
• 例如可以说北京和上海差不多距离 900 公里，但不是实际的精准距离
• 在地图导航的实际应用中，通常以当前地点到目标地点的直线距离作为 h
• A* 要保证最优性需要合适的 heuristic；admissible heuristic 要满足不为负且不高估真实最优剩余代价

例：上图展示了一个更新 4 节点的操作

1. 按照和 Dijkstra 算法完全一样的操作更新了 distTo 和 edgeTo 的值
2. 将 5 和 6 加入 PQ，但不再是按照 distTo 的大小排列，而是 distTo + h(v, goal)

演示链接