最短路问题

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

边权决定可采用的传播顺序。非负权让距离波前只能向外增长，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 }$。

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

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

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$ 路径。动态图、时间依赖权和多准则成本也需要另行规定更新接口与代价代数，不能从静态可加边权模型直接外推。