最短路径问题 · aiwiki.page

最短路径问题是图论和数学优化中的一个问题：在指定顶点之间寻找边权之和尽可能小的路线。权重可以表示距离、行程时间、成本或其他可累加的量，因此“最短”不一定意味着地理距离最短。在无权图中，目标是使经过的边数最少。这一问题是网络分析和高效算法设计的基础。(algs4.cs.princeton.edu)

数学表述

设 $G=(V,E)$ 为有限图，其顶点集为 $V$ ，边集为 $E$ ，权重函数为 $w:E\rightarrow\mathbb{R}$ 。在有向图中，每条边都必须沿其指定方向经过。对于路线 $P=(v_0,v_1,\ldots,v_k)$ ，其权重为

w(P)=\sum_{i=0}^{k-1}w(v_i,v_{i+1}).

给定源点 $s$ 和终点 $t$ ，若存在有限的最小路线权重，则最短路径距离 $\delta(s,t)$ 就是这一最小值。对于不可达的终点，通常约定其距离为 $+\infty$ 。多条不同的路线可能达到同一个最小值。(ocw.mit.edu)

术语的使用需要注意：简单路径不重复经过任何顶点，而游走可以重复经过顶点。标准的最短路径问题允许游走，但在不存在相关负权环时，可以选取一条简单路径作为权重最小的游走。负权环是边权之和为负的环。如果从 $s$ 可以到达这样的环，且从该环可以到达 $t$ ，那么反复绕环就能使路线成本任意降低；此时成本的下确界为 $-\infty$ ，而非有限的最短距离。图中其他位置的负权环未必影响这一特定顶点对。(ocw.mit.edu)

主要变体

单对最短路径问题只涉及一个源点和一个终点。单源最短路径问题求一个源点到所有顶点的距离，而全点对最短路径问题求每个有序顶点对之间的距离。将所有有向边反向，即可把单终点最短路径问题转化为单源最短路径问题。(ocw.mit.edu)

输出可以仅包含距离，也可以包含用于重建路线的前驱信息。如果源点到所有可达顶点都存在有限的最短路径，那么恰当地选择前驱，就能构成一棵最短路径树。这种紧凑的表示方式无需单独存储每条路线。(algs4.cs.princeton.edu)

最优子结构与松弛

最短路径具有最优子结构：最短路径上的任意连续子路径，也是其两端点之间的最短路径。否则，将该段替换为成本更低的路线，就会降低整条路径的总权重。这一性质既是动态规划建模的依据，也是正确性证明的基础。(ocw.mit.edu)

许多算法维护暂定距离 $d[v]$ ，初始时令 $d[s]=0$ ，其余值均为 $+\infty$ 。称为**边松弛**的操作检查一条边 $(u,v)$ ，并进行如下更新：

d[v]\leftarrow\min\bigl(d[v],\,d[u]+w(u,v)\bigr).

如果这一操作改善了距离估计，还会更新 $v$ 的前驱。各种算法的主要区别在于这些操作的执行顺序和次数。(ocw.mit.edu)

单源算法

算法的选择取决于边权和图的结构。令 $n=|V|$ 、 $m=|E|$ ，用大O记号表示的标准时间复杂度界如下：

条件	算法	时间复杂度
无权图或所有边权均为 1	[[breadth-first-search	广度优先搜索]]
[[directed-acyclic-graph	有向无环图]]	按拓扑顺序进行松弛
边权非负	使用二叉堆的[[dijkstra-algorithm	迪杰斯特拉算法]]
一般边权，支持负权环检测	[[bellman-ford-algorithm	贝尔曼–福特算法]]

这些复杂度界针对标准实现，并不涵盖所有可能的优化。(algs4.cs.princeton.edu)

广度优先搜索按照从源点出发所需边数递增的顺序探索顶点。有向无环图可以进行拓扑排序，从而在一个顶点的所有前驱都处理完毕后，再对该顶点的出边进行松弛；即使存在负权边，这一方法仍然适用。(algs4.cs.princeton.edu)

迪杰斯特拉算法通过优先队列反复选取暂定距离最小的顶点。边权非负保证了可以将这一距离确定为最终值；对于含有负权边的图，永久确定顶点距离的常规实现一般不能保证正确。贝尔曼–福特算法则反复遍历所有边。如果不存在从源点可达的负权环，经过 $n-1$ 轮遍历后，即可确定有限的最短距离；如果再进行一轮仍能改善距离，就表明存在从源点可达的负权环。(ocw.mit.edu)

全点对算法与启发式搜索

弗洛伊德–沃沙尔算法通过逐步允许更多顶点充当中间顶点，计算所有顶点对之间的距离。它采用如下递推式：

D^{(k)}_{ij} =\min\left(D^{(k-1)}_{ij}, D^{(k-1)}_{ik}+D^{(k-1)}_{kj}\right),

时间复杂度为 $O(n^3)$ ，空间复杂度为 $O(n^2)$ 。约翰逊算法提供了另一种方法，尤其适用于稀疏图：先用贝尔曼–福特算法求得顶点势函数，据此将边权重新赋值为非负数，同时保持最短路线的选择不变，再从每个源点分别运行迪杰斯特拉算法。(ocw.mit.edu)

对于指定终点，A* 搜索按 $f(v)=g(v)+h(v)$ 确定探索顺序，将从源点出发的已知成本与启发式评估函数给出的剩余成本估计相结合。可采纳的启发式函数不会高估实际剩余距离。一致的启发式函数还满足 $h(u)\leq w(u,v)+h(v)$ ，并且在目标点的值为零；这使图搜索能够在不重新展开已确定顶点的情况下获得最优解。令 $h=0$ ，便得到一致代价搜索。(cs.cmu.edu)

应用与实现

最短路径模型可用于交通路线规划、网络通信和状态空间搜索。开放最短路径优先路由协议使用迪杰斯特拉算法。要正确建模，权重必须表示所要优化的可累加目标：使距离最短和使行程时间最短，可能得到不同的路线。(algs4.cs.princeton.edu)

实现时，必须区分不可达顶点与距离很大但有限的顶点，并在出现并列最优结果时以一致的方式重建路线。浮点运算会产生舍入误差，而有限范围的整数运算在距离相加时可能溢出。数学上的正确性以这些运算能够保持松弛操作所依赖的比较结果为前提。(algs4.cs.princeton.edu)

参考来源

Shortest Pathsalgs4.cs.princeton.edu
Lecture 15: Shortest Paths I: Introocw.mit.edu
Lecture 15: Shortest Paths I: Introocw.mit.edu
Lecture 16: Shortest Paths II: Dijkstraocw.mit.edu
Algorithms and Data Structures Cheatsheetalgs4.cs.princeton.edu
BreadthFirstPaths (Algorithms 4/e)algs4.cs.princeton.edu
BellmanFordSP (Algorithms 4/e)algs4.cs.princeton.edu
Lecture 19: All-pairs Shortest Pathsocw.mit.edu
Search and Gamescs.cmu.edu