属于该分类的文章：

最短路径问题

6篇文章

SPFA 算法

Bellman‑Ford 算法用于求解带负权边的单源最短路径，允许边权为负，通过对所有边执行 n‑1 轮松弛操作得到最短路径；再执行一轮松弛，若仍可更新距离，说明图中存在负权回路，时间复杂度 O (nm)，效率低于 Dijkstra，适合检测负权环。

DAG 即有向无环图，DAG 上的最短路径先对图做拓扑排序，按照拓扑序列依次取出每个顶点，对它的所有出边执行松弛操作即可求出单源最短路径；该算法可以处理负权边，不能处理负环（DAG 本身不存在环），时间复杂度 O(n+m)，效率优于 Bellman‑Ford 与 SPFA。

Floyd‑Warshall 算法是基于动态规划的全源最短路径算法，可求解图中任意两点最短距离，支持负权边，适合小规模稠密图，也能够检测图中的负权环。

增量式 Floyd 在标准 Floyd 基础上，按顺序逐步加入中间节点 k，动态更新任意两点间最短路径，支持节点逐个新增的场景；它复用之前已算好的路径结果，不必每次从头完整重跑，适合图中节点不断增加的问题，时间复杂度仍为\(O(n^3)\)。

Dijkstra 算法是图论中经典的贪心算法，依托松弛操作求解非负边权带权图的单源最短路径，广泛运用于路径规划、网络路由等各类工程场景。

SPFA 是 Bellman‑Ford 的队列优化版本，用于求解带负权边的单源最短路径，只将被松弛成功的顶点入队，避免无效松弛；通过记录顶点入队次数，若某点入队超过顶点总数，即可判定存在负权回路，平均时间复杂度较低，最坏仍为 O (nm)。