形式陈述

带权图中，路径权重是边权之和；从源 $s$$s$ 到顶点 $v$$v$ 的最短路距离 $\delta(s,v)$$\delta (s,v)$ 是所有 $s\leadsto v$$s⇝v$ 路径权重的下确界，不可达时记为 $+\infty$$+\mathrm{\infty }$。若存在从 $s$$s$ 可达且还能到 $v$$v$ 的负权环，则没有有限最短路径，距离可降至 $-\infty$$-\mathrm{\infty }$。最短路满足最优子结构和三角不等式；松弛操作尝试用 $d[u]+w(u,v)$$d[u]+w(u,v)$ 改进 $d[v]$$d[v]$。算法选择取决于边权：非负权用 Dijkstra，任意无负环权用 Bellman–Ford，DAG 可按拓扑序。

直觉

最短路不是“边数最少”，而是在所有路线中累计代价最小。松弛逐步传播已知更便宜的前缀，直到所有必要约束 $d[v]\le d[u]+w(u,v)$$d[v]\le d[u]+w(u,v)$ 都稳定。

例子与边界

无权图可把每条边权设为 1，用 BFS 求最短边数。含负边时 Dijkstra 可能过早固定顶点而失败；Bellman–Ford 可处理负边并检测可达负环。零权环不破坏最短值，但可能产生无限多条等长最短路径。路径必须明确是否允许重复顶点；在无负环时总可取简单最短路径。多源问题可加一个零权超级源。

推论与应用

最短路建模路由、日程、差分约束、动态规划和网络优化，也是许多图算法正确性中“松弛 + 最短路径树”的核心范式。

参考资料

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, Introduction to Algorithms, 4th ed., MIT Press, 2022，Parts I–VI。
• Jon Kleinberg and Éva Tardos, Algorithm Design, Pearson, 2005，Chs. 1–13。