最短路问题

最短路按整条路线的可加成本比较，不按边数或某条局部最轻边决胜。松弛把一个已有前缀再延伸一步；当所有相关三角约束都稳定时，每个可达且不受负圈影响的顶点才得到最终距离。

边权决定可采用的传播顺序。非负权让距离波前只能向外增长，Dijkstra 因而可以永久结算最小候选；允许负边时，后来发现的路线可能反超早先候选，Bellman–Ford 要容许反复修正；DAG 没有回流，按拓扑序扫描一次即可，即使边权为负。

用游走定义 $\delta$ 可以如实表示负圈造成的无界下降。若只在有限多条简单路中取最小值，即使存在可利用的负圈也会返回一个有限数，从而掩盖“成本可任意降低”这一算法上不可忽略的事实。

弧 $s\to a$、$a\to t$、$s\to t$ 的权依次为 $2,3,6$ 时，路线 $s\to a\to t$ 的成本 $5$ 优于直达弧。把 $a\to t$ 改为 $-4$ 后，最短成本变为 $-2$；一条负边没有使问题失去定义，只使依赖非负性的结算方法不再可靠。若再加入 $t\to a$、权 $1$，则圈 $a\to t\to a$ 总权为 $-3$，从圈可达的 $a,t$ 距离均为 $-\mathrm{\infty }$。

在最初的非负权例子中，先松弛源点得到 $d[a]=2,d[t]=6$；再松弛 $a\to t$，候选值 $2+3=5$ 改进 $d[t]$，同时把 $t$ 的前驱改为 $a$。负边破坏结算的更直接反例是 $s\to a:2,s\to b:5,b\to a:-4$：若把距离 $2$ 的 $a$ 永久结算，后来经 $b$ 得到的真正最短距离 $1$ 就无法纠正。原图甚至无环，所以失败原因是非负权假设缺失，而非必须存在负圈。

若另有负圈 $x\to y\to x$，但 $x,y$ 从 $s$ 不可达，它不会影响这次单源查询；两点距离仍为 $+\mathrm{\infty }$。同样，可达负圈若不能再到达某个顶点 $v$，也不会把 $\delta (s,v)$ 变成 $-\mathrm{\infty }$。零权圈不会改变最短值，却会产生无限多条等成本最优游走；仍可删圈得到一条简单最短路。

请求多个不同答案时，必须重新约定输出身份。Yen算法理路Yen的k条最短简单路径Yen's algorithm · Yen k shortest loopless paths · Yen最短无环路径算法固定根前缀、禁止已经输出的同根下一边并删除根上的旧顶点，以跨轮候选堆枚举不同的简单路径，证明覆盖性并区分游走枚举。枚举禁止重复顶点的简单路径，有限多条耗尽后结束；Eppstein方法理路Eppstein的k条最短游走Eppstein k shortest paths · Eppstein sidetrack algorithm · k shortest walks用到终点的最短路树和非负偏离差价编码游走，通过共享偏离堆将无限候选空间改造成常数分支堆序树，按费用输出隐式记录。允许重复顶点，按弧ID序列区分游走，借偏离差价与共享堆输出有限k份隐式记录。零权环下可能已有无限多份最低成本答案，不能要求先输出这些再进入更贵一层，也不能把隐式记录成本冒充完整路线长度。

平行弧应保留各自权重与身份，不过只求距离时，同方向端点相同的弧只保留最小权者也不改变答案。无权图可把每条弧权设为 $1$，用 BFS 求最少弧数；多源问题可加入到各源的零权超级源。若成本依赖到达时刻、前一条边或不可相加的多重指标，就必须扩展状态或改变代价代数，普通最短路模型不再充分。

最轻奇支撑圈理路de Pina 支撑向量圈基算法de Pina minimum cycle basis algorithm · Support-vector minimum cycle basis · de Pina 最小圈基算法维护与已选圈正交的二元支撑，以双层最短路求最轻奇支撑圈，并通过基交换证明逐轮输出的圈基总权最小。把每个顶点扩成奇偶两层：经过标记边翻层，其他边留层。对全部原顶点v求(v,0)到(v,1)的最短路，再把最轻投影闭走提取为简单圈，得到圈基算法使用的oracle；只查一个起点或把重复边投影直接当圈都会漏掉证明义务。

Dijkstra理路Dijkstra 算法Dijkstra's algorithm在非负边权图中逐次确定最短距离的单源最短路算法。处理非负权单源情形，Bellman–Ford理路Bellman–Ford 算法Bellman–Ford algorithm通过反复松弛边求含负权边图的单源最短路并检测可达负环。允许负边并检测源可达负圈，Floyd–Warshall理路Floyd–Warshall 算法Floyd–Warshall algorithm以允许的中间顶点集合为阶段计算全部顶点对最短路。用矩阵动态规划求所有点对距离。Johnson 算法理路Johnson 全源最短路算法Johnson's algorithm · Johnson all-pairs shortest paths以 Bellman–Ford 势函数把无负环图重赋为非负边权，再重复 Dijkstra 求稀疏图全源最短路。先以势函数消去负边，再在稀疏图上逐源运行 Dijkstra；A*理路A* 搜索A* search · A-star search以已走代价与到目标的可采纳下界之和排序候选，并在一致性条件下保持最短路正确性的启发式搜索。面向单目标查询，用可证明的下界改变候选展开次序。这些算法求解同一模型的不同输入区域，权重假设不能互换。

最短路树与最小生成树理路最小生成树Minimum spanning tree · MST连通加权图中总边权最小的生成树及其算法问题。的目标不同。前者固定源点并分别最小化根到各顶点的距离；后者最小化整棵连接树的边权总和。三角形边权 $w(sa)=2,w(ab)=2,w(sb)=3$ 时，从 $s$ 的最短路树取 $sa,sb$，总权 $5$；MST 取 $sa,ab$，总权 $4$，但树上 $s$ 到 $b$ 的距离 $4$ 又大于原图的 $3$。

逐次最短路最小费用流理路最小费用流的逐次最短路法successive shortest path · SSP min-cost flow在残量网络反复沿最短费用路增广，并用顶点势保持约化费用非负。把最短路作为残量网络中的反复增广子程序，并用势维持约化成本非负；其目标是满足流量约束下的总费用最小，而非只输出一条 $s⇝t$ 路径。动态图、时间依赖权和多准则成本也需要另行规定更新接口与代价代数，不能从静态可加边权模型直接外推。

连续平面避障问题还需证明图模型没有漏掉最短路线：可见图理路可见图与多边形障碍最短路Visibility graph shortest path证明欧氏避障最短路只在多边形角点转弯，再把连续路径问题精确化为带几何可见边的图最短路。利用最短路只在多边形角点转弯的结构，构造精确图归约；无孔房间也可通过三角形通道和双链漏斗理路简单多边形最短路的漏斗算法Funnel algorithm在三角形通道上保存两条凹边界链，单向删点与移动 apex，在线性工作量内拉紧欧氏最短路。直接计算最短路。