最短路径

最短路径问题的答案不止一个算法——每个算法占据一段适用条件：非负权、负权、全源、有启发式。本章比较四个主流算法的适用条件与复杂度。

问题设定

给定带权图（边权可负与否决定一切）：

单源（SSSP）：从一点到所有点的最短路；
全源（APSP）：所有点对之间的最短路。

Dijkstra：非负权

贪心 + 优先队列（→ 堆与优先队列）：每次取当前距离最小的未定节点、松驰其出边。前提：边权非负——贪心的正确性（确定一个就不再变）依赖非负权。

堆优化后 $O((V+E) \log V)$ 。Dijkstra 在负权边上会给出错误答案：一个已经"确定"的节点可能被后来的负边更新，贪心前提被破坏。

import heapq

def dijkstra(adj, src):
    dist = {src: 0}
    pq = [(0, src)]
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist.get(u, float("inf")):   # 过期条目跳过
            continue
        for v, w in adj[u]:
            nd = d + w
            if nd < dist.get(v, float("inf")):
                dist[v] = nd
                heapq.heappush(pq, (nd, v))
    return dist

Bellman-Ford：负权与负环

对所有边反复松驰 $V-1$ 轮，第 $V$ 轮仍能松驰则存在负环。 $O(VE)$ ——比 Dijkstra 慢，但能处理负权并检测负环。负环检测是它的独有价值：货币套利检测（汇率图上找乘积 > 1 的环，取对数即负环）。

SPFA（队列优化的 Bellman-Ford）平均快，最坏仍是 $O(VE)$ ——竞赛中常用，工程中要记住最坏界。

Floyd-Warshall：全源

动态规划： $dp[k][i][j]$ = 只经过前 $k$ 个中转点的最短路，

dp[i][j] = \min(dp[i][j],\; dp[i][k] + dp[k][j]).

$O(V^3)$ 、 $O(V^2)$ 空间，三重循环十几行搞定。顶点数小（几百以内）时的全源首选；顶点大时对每个源跑 Dijkstra（ $V \cdot (V+E) \log V$ ）反而更好。传递闭包（可达性）是它的布尔版本。

A*：有启发式时

Dijkstra 的改进：优先队列按 $f(v) = g(v) + h(v)$ 排序， $g$ 是已知距离， $h$ 是到目标的启发式估计。A 的启发函数必须可采纳（不高估）**—— $h(v) \le$ 真实剩余距离——保证找到最短路；启发越紧（越接近真实值），扩展的节点越少。地图导航的直线距离（可采纳）是经典例子：A 只扩展朝目标方向的路径，远快于 Dijkstra 的四面扩展。

算法	复杂度	适用
Dijkstra（堆）	$O((V+E)\log V)$	非负权、单源
Bellman-Ford	$O(VE)$	负权、负环检测
SPFA	平均快，最坏 $O(VE)$	同上，竞赛用
Floyd-Warshall	$O(V^3)$	全源、小图
A*	依赖启发质量	单对端点、有可采纳启发

本章要点

非负权用 Dijkstra（堆优化 $O((V+E)\log V)$ ）；负权边上 Dijkstra 会给出错误答案
负权用 Bellman-Ford，并检测负环；SPFA 最坏仍是 $O(VE)$
全源小图用 Floyd-Warshall（ $O(V^3)$ ，十几行）；大图逐源 Dijkstra
*A 的启发函数必须可采纳（不高估）**；启发越紧扩展越少
选择逻辑：有无负权 → 单源还是全源 → 有无启发式