最短路径问题（从浅入深）

下面把最短路径问题按层次从概念、变体、常见算法、实现细节、优化与工程注意点一步步展开。会给出直观说明、复杂度、伪代码/可运行 Python 例子，以及常见陷阱与工程实践建议。

---

1) 问题描述与基本概念

问题（直观）：给定一个图（Graph），在图的顶点之间找到一条代价（weight，或长度）之和最小的路径。

基本要素

• 图 $G=(V,E)$ ：顶点集合 $V$、边集合 $E$。
• 边上有权重 $w(u,v)$（可以为正、非负、甚至负）；若无权则视为每条边权重为 1。
• 路径：一系列顶点连通的序列。代价为路径上边权之和。
• 输出可以是：最短距离（数值），或者最短路径（顶点序列），或二者。

常见变体

• 单源最短路（Single-Source Shortest Path，SSSP）：给定源点 $s$，求 $s$ 到所有顶点的最短距离/路径。
• 单对最短路（Single-Pair）：只求 $s$ 到 $t$。
• 全对最短路（All-Pairs Shortest Path，APSP）：任意两点之间的最短路（例如 Floyd–Warshall）。
• 带负边/负环的问题（需要检测负环）。
• 有向图 / 无向图；稀疏图 / 稠密图。
• K 最短路径（不只是最短一条，而是前 K 条简单路径或可能包含环的路径）。
• 动态图（图在运行时变化）或带约束的路径（如资源限制、多目标）。

---

2) 图的类型与算法选择的先决条件

• 无权或等权图：使用 BFS 得到单源最短路径（边权都相等）。
• 非负权重：Dijkstra（堆实现）是常用且高效的。
• 存在负权但无负环：Bellman–Ford 可解单源并能检测负环。
• 任意权重 / 全对：Floyd–Warshall（动态规划）或 Johnson（用 Dijkstra+重加权）。
• 启发式搜索（A*）：当你只关心单对（s->t）且能提供对目标有意义的启发式函数时，常用于路网、地图。
• 稠密图 vs 稀疏图：稠密图（|E|≈|V|^2）往往用邻接矩阵和 Floyd；稀疏图（|E|≈|V|）用邻接表 + Dijkstra（堆）更优。

---

3) 重要算法（原理 + 复杂度 + 实现提示）

3.1 BFS（无权图、单位权边）

• 原理：广度优先层次遍历，第一次访问节点的距离即最短距离（按跳数）。
• 复杂度：$O(V+E)$
• 输出：可记录 prev 数组恢复路径。
• 何时用：边权相同（或无权），例如社交网络跳数、未加权网格。

Python 伪实现

from collections import deque

def bfs_shortest_path(adj, s):
    # adj: dict or list of neighbors
    dist = {s: 0}
    prev = {s: None}
    q = deque([s])
    while q:
        u = q.popleft()
        for v in adj[u]:
            if v not in dist:
                dist[v] = dist[u] + 1
                prev[v] = u
                q.append(v)
    return dist, prev

–

🧩 一、BFS 的本质与适用范围

1.1 定义与本质

BFS（Breadth-First Search，广度优先搜索）是一种图遍历算法，它按“层次（Level）”从源点出发逐层访问相邻节点。

换句话说：

• 先访问距离源点 1 跳的所有节点，
• 再访问距离源点 2 跳的所有节点，
• 再访问距离源点 3 跳的所有节点……
  直到访问完所有可达节点。

1.2 BFS 适用的最短路径场景

BFS 用于无权图（Unweighted Graph） 或 所有边权相等的图（例如都为 1 或都为相同常数）。

为什么？因为 BFS 每前进一步（访问一层邻居）就相当于走了一条“代价相同的边”，
所以第一次到达一个节点时，走的路径必然是最短的（跳数最少）。

---

🧠 二、问题形式化描述

输入：

• 图 $G=(V,E)$，顶点集 $V$，边集 $E$
• 源点 $s\in V$

假设：

• 图无权，或每条边权重 = 1
• 图可以是有向或无向

输出：

• 最短距离：dist[v] = 从 s 到 v 的最小边数
• 最短路径：通过记录前驱（predecessor）数组可重构路径

性质：

• 若图连通，则 BFS 会访问到所有顶点；
• 若图不连通，则 BFS 仅能访问从 s 可达的部分。

---

⚙️ 三、算法原理（逐步推理）

3.1 思想

• 使用一个队列（FIFO），保证遍历是“层次式”的。
• 从源点 s 开始，访问所有邻居（距离为 1 的点）。
• 然后再访问这些邻居的邻居（距离为 2 的点）……如此类推。

3.2 状态记录

通常我们维护三个数组/字典：

1. dist[v]：s 到 v 的最短距离（单位权下即最少边数）
2. prev[v]：v 的前驱节点，用于重建路径
3. visited[v]：是否访问过（或用 dist 是否为 ∞ 判断）

3.3 步骤伪代码

BFS(G, s):
    for each vertex v in V:
        dist[v] = ∞
        prev[v] = None
    dist[s] = 0

    create queue Q
    enqueue(Q, s)

    while Q not empty:
        u = dequeue(Q)
        for each neighbor v of u:
            if dist[v] == ∞:        # v 未被访问
                dist[v] = dist[u] + 1
                prev[v] = u
                enqueue(Q, v)

3.4 关键点理解

• 队列保证层次访问：队列先进先出，使得先被发现的节点优先扩展。
• dist[v] = dist[u] + 1：每前进一步，路径长度加 1。
• 第一次访问节点即最短路径确定：因为 BFS 一层层推进，不可能存在更短路径在之后才发现。

---

💻 四、Python 实现（实用、可直接运行）

from collections import deque

def bfs_shortest_path(adj, start):
    """
    adj: dict, adjacency list {u: [v1, v2, ...]}
    start: starting node
    return: (dist, prev)
    """
    dist = {u: float('inf') for u in adj}
    prev = {u: None for u in adj}
    dist[start] = 0
    q = deque([start])

    while q:
        u = q.popleft()
        for v in adj[u]:
            if dist[v] == float('inf'):  # v 未访问
                dist[v] = dist[u] + 1
                prev[v] = u
                q.append(v)
    return dist, prev

def reconstruct_path(prev, start, goal):
    if prev[goal] is None and start != goal:
        return None
    path = []
    cur = goal
    while cur is not None:
        path.append(cur)
        cur = prev[cur]
    return path[::-1]

# 示例
if __name__ == "__main__":
    graph = {
        'A': ['B', 'C'],
        'B': ['A', 'D', 'E'],
        'C': ['A', 'F'],
        'D': ['B'],
        'E': ['B', 'F'],
        'F': ['C', 'E']
    }

    dist, prev = bfs_shortest_path(graph, 'A')
    print("最短距离：", dist)
    print("A 到 F 的最短路径：", reconstruct_path(prev, 'A', 'F'))

输出：

最短距离： {'A': 0, 'B': 1, 'C': 1, 'D': 2, 'E': 2, 'F': 2}
A 到 F 的最短路径： ['A', 'C', 'F']

---

📈 五、复杂度分析

指标	表达式	说明
时间复杂度	$O(V+E)$	每个顶点、每条边最多访问一次
空间复杂度	$O(V)$	存储队列、dist、prev

对稀疏图和稠密图均适用，因为 BFS 实际访问量取决于可达边数 E。

---

🔍 六、实例讲解（图示）

设图如下：

A -- B -- D
|    |
C -- E

从 A 出发：

• 层 0：A
• 层 1：B, C
• 层 2：D, E

BFS 过程：

队列	已访问	dist	prev
[A]	{}	A=0	None
[B,C]	{A}	B=1, C=1	prev[B]=A, prev[C]=A
[C,D,E]	{A,B}	D=2,E=2	prev[D]=B, prev[E]=B
[D,E]	{A,B,C}	…	…

最终：

• dist = {A:0, B:1, C:1, D:2, E:2}
• A→D 的路径重建：D←B←A → 路径 [A, B, D]

---

🧮 七、与其他算法的对比

特性	BFS	Dijkstra	Bellman–Ford
边权	相同 / 无权	非负	可负
时间复杂度	O(V+E)	O(E log V)	O(VE)
是否能处理负权	❌	❌	✅
实现复杂度	⭐ 简单	⭐⭐ 中	⭐⭐⭐ 较高
路径精度	最短跳数	最短代价	最短代价
是否贪心	否（层次式）	是	否（迭代松弛）

---

🛠️ 八、工程优化与应用场景

8.1 常见优化

• 标记 visited 而不是 dist==inf：节省浮点比较时间。
• 图稀疏：用邻接表（dict/list）；图稠密：用邻接矩阵。
• 搜索限制：若只需要某个目标节点，可在第一次找到它时直接停止 BFS。

8.2 典型应用

1. 最短跳数问题

   • 如社交网络最短好友链路、网页点击最短路径。

2. 网格最短路（迷宫）

   • BFS 在二维/三维栅格上最常用（每步代价相同）。

3. 连通性分析

   • BFS 可用于判断图是否连通、找连通分量。

4. 最少变换次数类问题

   • 如字符串变换（单词接龙问题）、棋盘搜索等。

5. 树的层序遍历（BFS 的特例）

---

⚠️ 九、常见错误与陷阱

错误	原因	修正
忘记标记访问	导致死循环（重复入队）	一旦入队即标记访问
不保存前驱	无法恢复路径	在更新 dist 时同时记录 prev
想用 BFS 求带权图	不适用	改用 Dijkstra
对无向图只存一向边	路径不完整	每条边需存两次 (u→v, v→u)
多源 BFS 处理不当	只初始化一个起点	初始化时多个源点同时入队、dist=0

---

💡 十、进阶拓展

1. 多源 BFS

   • 将多个源点同时入队（dist=0），即可求“从最近源点的距离”。

2. 双向 BFS

   • 对单对最短路径（s→t），从两端同时进行 BFS，在中间相遇，可大幅减少搜索空间。

3. 0-1 BFS

   • 若边权仅为 0 或 1，可用双端队列（deque）代替堆，复杂度仍为 O(V+E)，效果极佳。

---

✅ 总结

项目	说明
算法名称	BFS 最短路径
适用场景	无权图或等权图的最短路径
数据结构	队列（FIFO）
时间复杂度	O(V+E)
空间复杂度	O(V)
核心思想	按层次推进，第一次访问即最短路径确定
路径恢复	使用前驱数组回溯
优点	简单、快速、可拓展多源/双向
缺点	不适用于带权图

---

3.2 Dijkstra（非负权单源）

• 原理：贪心 + 优先队列。每次取当前未确定最短距离的最小距离节点并松弛其邻边。

• 复杂度：

  • 使用二叉堆（Python 的 heapq）：$O((V+E)\log V)$，一般写作 $O(E\log V)$（稀疏时）。
  • 使用 Fibonacci 堆可达 $O(V\log V+E)$，但实现复杂且常数较大。

• 要点：

  • 需要 非负边权；若存在负边会失败。
  • 使用邻接表更优。
  • 常见技术：在堆中插入 (dist,node) 的多版本，并在 pop 时跳过已过时条目（lazy deletion）。
  • 可记录 prev 恢复路径。

Python 实用实现（优先队列 + 路径重建）

import heapq

def dijkstra(adj, s):
    # adj: {u: [(v, weight), ...], ...}
    INF = float('inf')
    dist = {u: INF for u in adj}
    prev = {u: None for u in adj}
    dist[s] = 0
    heap = [(0, s)]
    while heap:
        d, u = heapq.heappop(heap)
        if d != dist[u]:
            continue
        for v, w in adj[u]:
            nd = d + w
            if nd < dist[v]:
                dist[v] = nd
                prev[v] = u
                heapq.heappush(heap, (nd, v))
    return dist, prev

def reconstruct_path(prev, s, t):
    if prev[t] is None and s != t:
        return None
    path = []
    cur = t
    while cur is not None:
        path.append(cur)
        cur = prev[cur]
    return path[::-1]

Dijkstra 算法（非负权单源最短路径）

---

🧩 一、问题与核心思想

1.1 问题定义（Single-Source Shortest Path, SSSP）

给定：

• 一个加权有向图 $G=(V,E)$
• 每条边 $(u,v)\in E$ 有一个非负权重 $w(u,v)\ge 0$
• 一个源点 $s\in V$

目标：

求出从源点 $s$ 到所有其他顶点 $v\in V$ 的最短路径距离 $d[v]$，并能恢复具体路径。

---

1.2 Dijkstra 的核心直觉

Dijkstra 的思想源于 BFS 的推广：

对比点	BFS	Dijkstra
图类型	无权图 / 等权图	边权非负、可不同
距离定义	边数（层次）	边权之和
数据结构	队列（FIFO）	优先队列（堆）
扩展顺序	按层次	按当前最短距离

核心思想：

每次选择当前未确定的、距离源点最近的节点，将其“距离”固定（最短路径已确定），然后用它去更新（松弛）邻居节点。

---

🧠 二、数学与算法逻辑

2.1 定义与初始化

• $d[v]$：当前已知的从 $s$ 到 $v$ 的最短距离（初始为 ∞）
• $prev[v]$：最短路径中 $v$ 的前驱节点（用于重建路径）
• 源点初始化：
  $d[s]=0$，其他节点 $d[v]=\infty$

2.2 “贪心”思想核心

Dijkstra 的贪心选择性质：

如果所有边权都非负，那么在每一步选出当前距离最小的未处理节点，它的最短距离已经确定，不会再被更新。

原因：
因为任何经过其他未确定节点的路径都至少不比当前更短（由于非负权）。

---

⚙️ 三、算法流程（详细步骤）

1. 初始化：

   • 对每个节点 v：dist[v] = ∞, prev[v] = None
   • 源点 s：dist[s] = 0
   • 创建最小堆（优先队列）并放入 (0, s)

2. 主循环：

   • 从堆中取出距离最小的节点 u（若已处理过则跳过）

   • 对每个邻居 v：

     • 若 dist[u] + w(u,v) < dist[v]：

       • 更新 dist[v]
       • 记录前驱 prev[v] = u
       • 将 (dist[v], v) 入堆

3. 结束条件：

   • 所有节点都确定，或堆为空。

4. 路径恢复：

   • 从目标节点 t 反向沿着 prev 回溯，得到路径。

---

💻 四、Python 实现（优先队列版）

import heapq

def dijkstra(adj, start):
    """
    adj: dict {u: [(v, w), ...]}  邻接表
    start: 源点
    return: (dist, prev)
    """
    INF = float('inf')
    dist = {u: INF for u in adj}
    prev = {u: None for u in adj}
    dist[start] = 0

    heap = [(0, start)]  # (当前距离, 节点)
    while heap:
        d, u = heapq.heappop(heap)
        # 若堆中该记录已过期（有更短距离出现），跳过
        if d != dist[u]:
            continue
        for v, w in adj[u]:
            nd = d + w
            if nd < dist[v]:
                dist[v] = nd
                prev[v] = u
                heapq.heappush(heap, (nd, v))
    return dist, prev

def reconstruct_path(prev, s, t):
    if prev[t] is None and s != t:
        return None
    path = []
    cur = t
    while cur is not None:
        path.append(cur)
        cur = prev[cur]
    return path[::-1]

# 示例
if __name__ == "__main__":
    graph = {
        'A': [('B', 1), ('C', 4)],
        'B': [('C', 2), ('D', 5)],
        'C': [('D', 1)],
        'D': []
    }

    dist, prev = dijkstra(graph, 'A')
    print("最短距离：", dist)
    print("A 到 D 的最短路径：", reconstruct_path(prev, 'A', 'D'))

输出：

最短距离： {'A': 0, 'B': 1, 'C': 3, 'D': 4}
A 到 D 的最短路径： ['A', 'B', 'C', 'D']

---

📊 五、复杂度分析

操作	次数	每次复杂度	总计
弹出最小节点	$V$	$O(\log V)$	$O(V\log V)$
松弛邻边	$E$	$O(\log V)$	$O(E\log V)$

✅ 总时间复杂度：

$$O((V+E)\log V)\approx O(E\log V)$$

（通常 E ≥ V）

✅ 空间复杂度：

$$O(V)$$

用于存储 dist、prev、堆、邻接表。

---

🔍 六、运行示意（图例）

设有如下加权有向图：

    (1)
A ------> B
|         |
|         | (5)
|         v
| (4)     D
v
C -------->
   (1)

步骤：

步骤	取出节点	更新邻居	dist 结果
初始化	—	—	A=0, 其余=∞
1	A	B=1, C=4	B=1, C=4
2	B	C=3, D=6	C=3, D=6
3	C	D=4	D=4
4	D	—	结束

最终最短距离：

A:0, B:1, C:3, D:4

路径 A→B→C→D。

---

🧮 七、算法正确性（贪心证明简述）

贪心不等式性质：

若图中所有边权均 ≥ 0，则当某个节点 u 的最短路径确定（即当前堆顶），
其最短距离 dist[u] 不可能再被改进。

证明思路：

1. 若存在更短路径通过其他节点 v（尚未确定），
   那么 dist[v] + w(v,u) < dist[u]。
2. 但 v 还没被选中，意味着 dist[v] ≥ dist[u]（因为堆顶 u 最小）。
3. 所以矛盾。
   ⇒ dist[u] 已经是全局最短。

---

⚙️ 八、Dijkstra 的几种实现版本

版本	数据结构	复杂度	适用场景
数组版	顺序扫描找最小点	O(V²)	小图、稠密图
二叉堆	heapq（常用）	O(E log V)	稀疏图
Fibonacci 堆	理论最优 O(V log V + E)	复杂，实践少见
索引堆	自实现 decrease-key	高性能工程实现

---

🧠 九、常见扩展与优化

9.1 终止提前（单目标优化）

若只关心 s → t 的最短路径，则可在取出目标节点 t 后立即退出循环。
（因为当它出堆时已确定最短路径）

---

9.2 图存储优化

• 稀疏图：邻接表（dict/list of edges）
• 稠密图：邻接矩阵（二维数组）
• 对无向图：每条边存两次（u→v 和 v→u）

---

9.3 Lazy vs Decrease-key 实现

Python 的 heapq 不支持堆内更新（decrease-key），常用 Lazy 删除：

每当发现更短路径时重新 push (new_dist, node)，
弹出时若旧距离无效则跳过。

此方法代码简单但堆中会有重复项，空间略增，性能仍足够好。

---

9.4 结合 A* 启发式（A* = Dijkstra + 启发）

若只求单对最短路径，可加上启发式函数 h(v)，
让优先队列比较 f(v) = g(v) + h(v)（A* 算法）。
启发式低估真实距离时，仍能保证最优。

---

📈 十、算法局限与注意点

限制/问题	说明	解决方法
含负边权	会出错（贪心假设失效）	改用 Bellman–Ford
浮点权重	存在数值误差	使用容差比较
内存问题	大图时 dist/prev 占用大	稀疏存储或分块计算
不可达节点	dist[v] 仍为 ∞	判断并排除

---

🛠️ 十一、实际工程应用

场景	应用示例
地图导航	Google Maps, 高德路径规划
网络路由	OSPF、IS-IS 协议内部使用 Dijkstra
游戏寻路	RTS 游戏单位移动（无启发式时）
电路/物流优化	最短连线、最少成本传输
操作系统调度	最短响应时间策略

---

⚠️ 十二、常见错误与陷阱

错误	原因	修正
存在负边	算法假设破坏	改用 Bellman–Ford
重复入堆不判断	性能浪费	Lazy 删除 or visited
没存前驱	无法恢复路径	在松弛时更新 prev[v]
不初始化 dist[s]=0	无法正确起步	初始化时赋 0
无向图边只加一边	图不完整	每条边加两次 (u→v, v→u)

---

🧩 十三、例子总结（视觉化）

假设图如下（边权非负）：

A--1--B--2--C
|      \
4       5
|        \
D---1-----E

求 A→E 最短路径。

• 初始化：dist[A]=0，其余∞

• 出堆顺序：A → B → D → C → E

• 最终结果：

  • 距离：A→B→E = 6
  • 路径：[A, B, E]

---

✅ 十四、总结表格

项目	内容
算法名称	Dijkstra
目标	单源最短路径（非负边权）
数据结构	优先队列（最小堆）
时间复杂度	O(E log V)
空间复杂度	O(V)
核心思想	贪心选择 + 松弛更新
优点	高效、精确、工程常用
缺点	不能处理负边权
路径恢复	使用 prev 数组反向回溯

---

🎯 十五、进一步方向

• Johnson 算法：用 Dijkstra 组合处理全对最短路径（加重加权）。
• A*：加入启发式函数，用于单目标路径搜索。
• Bidirectional Dijkstra：从起点和终点同时进行，速度更快。
• 动态 Dijkstra：当边权更新时，部分重用旧结果。

---

3.3 Bellman–Ford（允许负边，检测负环）

• 原理：松弛操作对所有边做 $|V|-1$ 轮；之后一轮如果还能松弛说明存在负环。
• 复杂度：$O(VE)$。
• 适用：图较小或必须支持负权；能检测并定位负权回路。
• 局限：慢，不适合大型稀疏图。

伪代码（Python）

def bellman_ford(edges, V, s):
    # edges: list of (u, v, w)
    INF = float('inf')
    dist = [INF]*V
    prev = [None]*V
    dist[s] = 0
    for _ in range(V-1):
        updated = False
        for u,v,w in edges:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                prev[v] = u
                updated = True
        if not updated:
            break
    # detect negative cycle
    for u,v,w in edges:
        if dist[u] + w < dist[v]:
            raise ValueError("Graph contains a negative-weight cycle")
    return dist, prev

3.4 Floyd–Warshall（全对最短路，任意权重）

• 原理：动态规划，三层循环，逐步允许中间顶点集合为 {0..k}。
• 复杂度：$O(V^3)$。实现简单，适用于 $V\lesssim 400$（取决硬件）。
• 可扩展到路径重建（next 矩阵或 next[u][v] 保存下一跳）。

伪代码框架

# dist initialized with INF, dist[u][u] = 0
# next[u][v] = v if edge u->v exists else None
for k in range(n):
    for i in range(n):
        for j in range(n):
            if dist[i][k] + dist[k][j] < dist[i][j]:
                dist[i][j] = dist[i][k] + dist[k][j]
                next[i][j] = next[i][k]

3.5 Johnson（稀疏图的 APSP）

• 思路：对图加一个超源 s’ 连到所有节点边权 0，运行 Bellman–Ford 找到重加权值 $h[v]$，使得新权 $w^{\prime }(u,v)=w(u,v)+h[u]-h[v]$ 非负，然后对每个顶点运行 Dijkstra（非负权），最后还原距离。复杂度 $O(VE+VE\log V)$（或写作 $O(VE+V\cdot E\log V)$），对稀疏图常优于 Floyd。

3.6 A*（启发式单对搜索）

• 原理：将启发式函数 $h(x)$ 加入优先级（f = g + h），g 为已知从 s 到 x 的距离，h 为 x 到 t 的估计（低估），若 h 为一致可保最优。
• 何时用：地图、网格、路由中 s->t，并可提供良好启发（例如欧氏距离）。
• 性能：如果启发好，能大幅剪枝；最坏仍可能退化为 Dijkstra。
• 要求：启发式要可接受（admissible）（即永不高估真实距离）保证最优；一致（consistent）则能简化实现（避免重复处理）。

A* 伪代码（类似 Dijkstra，仅比较 f = g + h）

def a_star(adj, start, goal, h):
    open_heap = [(h(start), 0, start)]  # (f, g, node)
    g_score = {start: 0}
    prev = {start: None}
    while open_heap:
        f, g, u = heapq.heappop(open_heap)
        if u == goal:
            return reconstruct(prev, start, goal)
        for v, w in adj[u]:
            tentative_g = g + w
            if tentative_g < g_score.get(v, float('inf')):
                g_score[v] = tentative_g
                prev[v] = u
                heapq.heappush(open_heap, (tentative_g + h(v), tentative_g, v))
    return None

3.7 SPFA（队列版 Bellman，短路优化版）

• 思路：按需松弛并把需要松弛的节点入队；在许多实际图上快，但在特定构造下会退化到 Bellman–Ford 的最坏 $O(VE)$ 或更糟，可能被恶意构造卡住（变成指数）。
• 建议：谨慎使用，若用请加负循环检测和最大入队次数限制。

---

4) 路径重建（通用做法）

• 在松弛时维护 prev[v] = u（即到 v 的最短路径的前驱）。
• 到达 t 后，从 t 反向追溯到 s 得到路径 —— 然后反转。
• 注意负权或 Bellman–Ford 时，如果存在负环，路径重建可能无意义（路径长度可无限减少）。

---

5) 算法复杂度汇总（常见情况）

• BFS（无权）：$O(V+E)$
• Dijkstra（邻接表 + 二叉堆）：$O((V+E)\log V)\approx O(E\log V)$
• Bellman–Ford：$O(VE)$
• Floyd–Warshall：$O(V^3)$
• Johnson：$O(VE+V\cdot E\log V)$（更常写成 $O(VE+V\cdot E\log V)$，针对稀疏图优）
• A*：最坏情况同 Dijkstra，但常更快（依赖启发）
• SPFA：平均快，最坏糟糕（可退化）

---

6) 常见工程注意点与优化技巧

1. 数据结构

   • 对于大规模稀疏图，使用邻接表（链表或列表 + 对应权重）。
   • 使用合适的堆（binary heap 足够；C++ 的 priority_queue，Python 的 heapq）。
   • 如果需要减少内存，可用索引节点（0…n-1）替代哈希表键。

2. 懒惰删除 vs 减少 decrease-key

   • Python heapq 没有 decrease-key；通常用“将新距离推入堆，多版本入堆并在 pop 时检查是否为当前最小”方式（lazy）。
   • 对性能有极限要求时，可以用 heapdict、自编配对堆或 Fibonacci 堆（罕见）。

3. 浮点权重

   • 若使用浮点权重，注意数值稳定性与比较 eps 问题。
   • 对浮点代价，使用 math.isclose 或在比较时加 eps。

4. 负权处理

   • 若图可能含负权且你需要单源，使用 Bellman–Ford。
   • 若要求全对且有负权但无负环，Johnson 比 Floyd–Warshall 在稀疏图上更优。

5. 启发函数的设计（A*）

   • 需低估真实代价（admissible）才保证最优。
   • 在网格/欧氏空间常用欧氏距离或曼哈顿（取决于运动规则）。

6. 内存 vs 时间的折中

   • Floyd–Warshall 使用 $O(V^2)$ 内存；Dijkstra 单次使用 $O(V)$。
   • APSP 的实现要权衡是否需要返回全部路径。

7. 并行/分布式

   • 对超大图（网页级别）使用并行/分布式算法（如基于 Pregel/GraphX 的最短路径近似或分布式 Bellman/Floyd 变体）。
   • 权衡精度与通信开销；常需要近似或多次迭代收敛算法。

8. 动态/增量图

   • 对于频繁增删边的图，可用增量最短路算法或维护可重用信息（例如动态树/替代路径结构），但实现复杂。

---

7) 示例：完整的 Dijkstra 示例（含路径恢复）——可直接用在工程里

import heapq

def dijkstra(adj, start):
    """
    adj: dict {u: [(v, w), ...], ...}
    returns (dist, prev)
    dist: dict of shortest distances from start
    prev: dict of predecessors for path reconstruction
    """
    INF = float('inf')
    dist = {u: INF for u in adj}
    prev = {u: None for u in adj}
    dist[start] = 0
    heap = [(0, start)]

    while heap:
        d,u = heapq.heappop(heap)
        if d != dist[u]:
            continue
        for v,w in adj[u]:
            nd = d + w
            if nd < dist[v]:
                dist[v] = nd
                prev[v] = u
                heapq.heappush(heap, (nd, v))
    return dist, prev

def reconstruct_path(prev, start, goal):
    if prev[goal] is None and start != goal:
        return None
    path = []
    cur = goal
    while cur is not None:
        path.append(cur)
        cur = prev[cur]
    return path[::-1]

# Example usage:
if __name__ == "__main__":
    adj = {
        'A': [('B',1), ('C',4)],
        'B': [('C',2), ('D',5)],
        'C': [('D',1)],
        'D': []
    }
    dist, prev = dijkstra(adj, 'A')
    print("Distances:", dist)
    print("Path A->D:", reconstruct_path(prev, 'A', 'D'))

---

8) 扩展话题（若你想更深入）

• K 最短简单路径（Yen、Eppstein）：找到前 K 条互不重复顶点的最短路径（复杂但常用在路由/推荐）。
• 最短路与流（最小费用最大流）：在流网络里求带费用的流，使用 SPFA / Bellman–Ford / Dijkstra（带可行潜势）。
• 替代路径/敏感性分析：若某条边故障，最短路径如何改变？可用于鲁棒性分析。
• 随机/近似算法：在超大图上，用近似/样本技术估计最短路径（trade time for accuracy）。
• 多目标最短路（Pareto 最优）：边上有多个属性（距离、时间、费用），求非支配解集。

---

9) 常见问答（FAQ）

• Q：Dijkstra 能否处理 0 权重或 0/正权？
  A：可以，0 权重不影响正确性（只要无负权）。

• Q：为什么 Dijkstra 不能处理负边？
  A：Dijkstra 假设一旦从堆中弹出某顶点的最短距离就是确定的；若存在负边，后续可能再找到更短路径，从而破坏贪心正确性。

• Q：如何处理无向带权图？
  A：把每条无向边 $u-v$ 视为两条有向边 $u\to v$ 与 $v\to u$。

• Q：什么时候用 Floyd–Warshall？
  A：顶点数 $V$ 不大且需要全对最短路径时；或需要计算任意两点之间的最短路和路径重建很方便。

---

10) 总结建议（工程实践）

• 小图或需要全对：用 Floyd（实现简单）或 Johnson（若稀疏）。
• 常见单源且权非负：Dijkstra（邻接表 + heap）。
• 需要处理负边：Bellman–Ford（并检测负环）；若规模大，慎用。
• 单对并有启发：A*（设计好启发函数）。
• 关注性能：用邻接表、避免不必要重复松弛、用合适堆结构。
• 在实现中始终保留 prev 用于路径重建，并做好异常/边界条件（不可达、负环）的处理。

---