非常好，“单源最短路问题”是图论与算法中的重要经典问题之一。在深入数据结构或算法学习中，这是理解“权值图 + 贪心 / 动态规划思想”的重要节点。下面我将为你完整整理这一章节的内容，标题为：

《领略算法真谛》

单源最短路问题——解构路径的最优解

📘 一、什么是单源最短路问题？

定义：在一个带权有向或无向图中，给定一个源点 s，求从 s 到图中所有顶点的最短路径（路径权值和最小）。

  • 输入：图 G=(V,E)、源点 s、边权重 w(u,v)≥0
  • 输出：从源点 s 到所有其它顶点的最短路径及其路径长度

🛣️ 二、经典算法总览

算法适用图类型时间复杂度特点
Dijkstra非负权图O((V+E) log V)贪心，效率高，常用
Bellman-Ford可含负权边O(VE)可检测负权环
SPFABellman-Ford优化平均较快某些图极快，最坏 O(VE)
Floyd所有点对点最短路O(V³)静态图处理

🧠 三、Dijkstra 算法详解（重点）

✅ 1. 算法思想

使用贪心策略，逐步扩展最短路径集合。

  • 初始将源点加入“已确定集合”
  • 每次选择离源点最近的未访问节点
  • 更新它的邻居的最短路径估计
  • 重复直到所有点确定最短路径

✅ 2. 伪代码（使用优先队列优化）

import heapq

def dijkstra(graph, start):
    dist = {v: float('inf') for v in graph}
    dist[start] = 0
    visited = set()
    heap = [(0, start)]
    
    while heap:
        d, u = heapq.heappop(heap)
        if u in visited:
            continue
        visited.add(u)
        for v, w in graph[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                heapq.heappush(heap, (dist[v], v))
    
    return dist

✅ 3. 图示说明（描述）

假设图如下：

     2       1
A ------ B ------ C
 \       |
  \5     |3
   \     v
    ------ D
  • 源点 A
  • 初始：dist[A]=0, 其它无穷大
  • 每次选择当前 dist 最小的点扩展路径

🧨 四、Bellman-Ford 算法详解（处理负权图）

✅ 1. 核心思想

  • 动态规划，每轮尝试“松弛”所有边
  • 共执行 V-1 轮松弛，确保最短路径
  • 第 V 轮再松弛一次，若还能更新则说明有负权环

✅ 2. 使用场景

  • 图中有负权边，不能用 Dijkstra
  • 适用于金融、货币兑换等涉及负值的图模型

⚡ 五、SPFA（Shortest Path Faster Algorithm）

是 Bellman-Ford 的队列优化版本，平均效率比 Dijkstra 还快

✅ 思路：

  • 每次只处理在队列中的点
  • 避免无谓松弛，适用于稀疏图
  • 可能退化成 Bellman-Ford，最坏 O(VE)

🧮 六、算法对比图表

特性DijkstraBellman-FordSPFA
负权边支持❌✅✅
是否稳定（一定最短）✅✅✅
是否贪心策略✅❌❌
是否可检测负环❌✅✅
时间复杂度O((V+E)logV)O(VE)平均 O(E)

📌 七、实际应用场景举例

场景描述
地图导航Dijkstra 最常见，用于地图系统 GPS
网络延迟优化求最短时延路径
货币兑换Bellman-Ford 检测套利环
电信路由优化SPFA 处理大规模路由计算
游戏AI路径规划简化版 Dijkstra 用于角色寻路

🧭 八、总结口诀

最短路径靠贪心，负权要用 Bell；Dijkstra 用堆加速，SPFA 帮你省时间。