1 基本概念
最短路算法研究的是图中两点之间总代价最小的路径。这里的代价通常由边权累加得到，可以表示距离、时间、费用、风险等。由于建模灵活，这类问题既出现在理论图论中，也广泛用于导航、通信、调度与规划等实际场景。
1.1 图与路径
图是最短路问题的基本载体，通常由点和边构成。路径则表示沿着若干边从一个点到另一个点的行走过程。不同的图类型和路径定义，会直接影响最短路的求解方式与结果解释。
1.1.1 点、边与权重
在图中，点表示对象或位置，边表示它们之间的连接关系。若边带有数值，通常称为权重或边权，用来刻画经过该边的代价。最短路问题往往假设路径总代价等于所经边权之和，但在某些扩展模型中，也可能采用最大值、乘积或其他组合方式。
1.1.2 路径、简单路径与回路
路径是按边连接的一串顶点序列。若一条路径中顶点不重复，通常称为简单路径。若路径起点和终点相同，则构成回路。多数经典最短路问题在无负环条件下，最优解可以看作简单路径或不含无意义绕行的路径，因为重复经过正权回路不会降低总代价。
1.2 最短路问题定义
最短路问题的核心，是在给定图与权重后，寻找满足约束条件的最小代价路径。根据起点、终点和查询范围不同，常见问题可分为单源、单终点和全源三类。
1.2.1 单源最短路
单源最短路是从固定起点出发，求到图中其他所有点的最短距离。它是应用最广的一类形式，适合一次出发、多点查询的场景，例如从某个仓库到所有配送点的最小成本计算。
1.2.2 单终点最短路
单终点最短路关注“所有点到指定终点”的最短距离。若图是有向图，通常可将边方向反转后，转化为单源最短路求解。这种处理在反向可达分析、终点导向规划中较常见。
1.2.3 全源最短路
全源最短路要求任意两点之间的最短距离都被求出。它适合点数较少但查询频繁的系统，例如小规模网络分析、稠密关系图统计等。常见方法包括多次单源求解与专门的全源算法。
1.3 最短路存在性与唯一性
最短路是否存在、是否唯一，取决于图的连通性、权值分布以及是否存在负环等因素。理论上，若某些条件不满足，最短距离可能无法定义或无法稳定求得。
1.3.1 不连通图中的情形
若起点与终点之间不存在连通路径，则最短路不存在，通常记为无穷大或不可达。在实现中，常用一个足够大的初始值表示未被到达的状态。对于多源或全源问题，不连通部分需要单独保留为不可达信息。
1.3.2 多条等长最短路径
有时从起点到终点会存在多条代价相同的最短路径。这并不影响最短距离本身，但会影响路径恢复结果。若需要输出一条具体路径，通常由算法更新顺序、邻接顺序或额外规则决定；若需要所有最优方案，则要保存更多前驱信息。
1.3.3 负权边与负环影响
当边权允许为负时，路径总代价可能被进一步降低，相关算法必须更谨慎处理。若图中存在可达负环，则沿环反复绕行可使路径代价无限减小，此时最短路通常不再有有限意义。因此，带负权边的问题往往还需配合负环检测。
2 经典算法
最短路算法按图的权值特征可分为多个经典分支。对于无权或单位权图，通常使用广度优先搜索；对于非负权图，常用 Dijkstra；若存在负权边，则常见 Bellman-Ford 与 SPFA；而全源问题则常用 Floyd-Warshall 或 Johnson。
2.1 无权图与单位权图算法
在无权图中，每条边的代价相同，最短路等价于边数最少的路径。若所有边权都相等，也可视为单位权图处理，此时很多问题可转化为分层扩展后的普通搜索。
2.1.1 广度优先搜索
广度优先搜索按层扩展结点，天然保证第一次到达某点时使用的边数最少，因此适用于无权图最短路。其实现简单，时间效率高，在迷宫、网格、社交层级等问题中非常常见。
2.1.2 多源 BFS
多源 BFS 是将多个起点同时入队，向外同步扩展。它适用于多个初始位置共同影响全图的场景，例如最近资源点、扩散时间、距离最近的出口等问题。此时每个点的最短距离对应于距离最近的源点。
2.2 非负权图算法
当边权为非负数时，可以使用基于贪心思想的最短路算法。该类算法的核心是：每次优先确定当前距离最小且尚未定型的点，从而逐步扩展出全局最优解。
2.2.1 Dijkstra 算法
Dijkstra 算法是非负权单源最短路的代表方法。它通过不断选择当前暂定距离最小的顶点，并对其邻边进行松弛来推进结果。由于非负权保证了已确定距离不会被后续路径改写，因此算法具有严格正确性。
2.2.2 堆优化与优先队列实现
使用优先队列维护当前最小距离候选点，可以显著降低 Dijkstra 的总体复杂度。常见实现中，堆中可能存在重复条目，因此通常配合“距离不一致则跳过”的写法。对于稀疏图，这种实现方式尤为高效。
2.2.3 朴素实现与适用场景
朴素版 Dijkstra 采用线性扫描寻找当前最小点，代码较短，便于理解和调试。当图较小或边数不多时，这种方法完全可用。尽管复杂度较高，但在教学、验证和数据规模有限的场景中仍有价值。
2.3 含负权边算法
若图中存在负权边，贪心定型策略不再可靠，需要使用能多轮修正距离的算法。此类方法通常基于反复松弛，直到不存在可改进的边为止。
2.3.1 Bellman-Ford 算法
Bellman-Ford 通过重复遍历所有边进行松弛，最多进行若干轮后即可得到单源最短路结果。它能处理负权边，并可顺带判断负环。由于逻辑直接、结构清晰，常被视为负权最短路的基础算法。
2.3.2 SPFA 算法
SPFA 是 Bellman-Ford 的队列优化版本，通常只把可能发生更新的点加入队列，减少无效松弛。平均表现往往较好，但在某些构造数据上可能退化。它在竞赛和工程中都较常见，尤其适合中等规模图。
2.3.3 负环检测
负环检测的目的，是判断从源点可达范围内是否存在总权值为负的环。常见做法是记录每个点被松弛或入队的次数，当次数超过阈值时可判定存在负环。若负环成立，则某些最短路结果没有有限意义。
2.4 全源最短路算法
全源最短路关注任意两点之间的距离矩阵，适用于需要大量查询的场景。与多次单源求解相比，专门的全源算法有时更简洁，也更适合中小规模图。
2.4.1 Floyd-Warshall 算法
Floyd-Warshall 是典型的三重循环动态规划算法，逐步考虑是否允许某个中间点作为转移节点。它能够求解全源最短路，并可处理负权边，但通常不适合含负环的情形。该算法实现统一，适用于点数较小且边较密的图。
2.4.2 Johnson 算法
Johnson 算法通过一次势能重标定，将带负权但无负环的图转化为非负权图，再对每个源点执行最短路计算。它将负权处理与多源查询结合起来，在稀疏图全源问题中具有较好的综合表现。
2.4.3 稠密图与稀疏图的选择
稠密图中边数接近顶点数平方，全源动态规划类算法往往更自然；稀疏图中边数较少，多次单源或 Johnson 算法通常更具优势。实际选择时，需要综合顶点规模、边密度、是否存在负权以及查询次数。
3 图模型与问题变体
最短路不仅取决于算法，还取决于图如何建模。不同的边方向、权值形式和附加约束，会把同一现实问题映射为不同的图论模型。
3.1 有向图与无向图
有向图中的边具有方向，表示关系是单向的；无向图中的边则可双向通行。最短路算法在两类图上都能使用，但建模细节会影响边的存储和转移方式。
3.1.1 双向边建模
无向图通常可以拆成两条方向相反、权值相同的有向边来存储。这样做便于统一实现，也能直接复用有向图上的最短路代码。对于某些实际系统，还可以为两个方向设置不同代价，以表达上下坡、逆行限制等情况。
3.1.2 单向可达性处理
在有向图中，某些点之间可能只能单向到达。处理此类问题时，需要特别注意边方向与可达性判断。若要从终点反向分析可达范围，通常会构造反图，以便把“到终点”转化为“从终点出发”。
3.2 特殊权值与约束
现实问题中的边权并不总是严格正数，也可能出现零权、多重边、自环或动态变化。针对这些情况，需要在算法和实现上做相应调整。
3.2.1 零权边处理
零权边不会增加路径总代价，但可能导致大量等价路径或复杂的松弛传播。使用非负权算法时，零权边一般是允许的；但在某些结构中，若零权环与状态扩展同时存在，需注意避免重复访问造成的效率问题。
3.2.2 多重边与自环
多重边是指同一对点之间存在多条边，自环则是从点到自身的边。最短路算法通常可以直接处理多重边，但自环在无负环场景下通常不会带来更优结果。若自环权值为负，则可能构成负环的一部分，需要重点检查。
3.2.3 动态权值情形
当边权会随时间、状态或外部条件变化时，最短路问题就不再是一次性静态求解。此时常需引入动态维护、分时段建模或状态扩展方法，以适配实时变化的成本结构。
3.3 路径约束变体
一些问题不仅要求最短，还附带边数、经过节点或备选路径等限制。这类变体常通过扩展状态、增加层次或引入额外优化目标来解决。
3.3.1 限制边数的最短路
若路径必须满足边数上限，不能直接使用普通最短路结果。常见做法是把“已走边数”作为状态的一部分，形成分层图或动态规划表，从而在约束内求最优解。
3.3.2 必经点与指定终点
当路径需要经过某个特定节点时，通常可拆分为“起点到必经点”和“必经点到终点”两段分别求解，再合并代价。若还有顺序约束或多个必经点，则问题会进一步复杂，常与状态压缩结合使用。
3.3.3 第二短路与 k 短路
第二短路指除最短路外的次优路径，k 短路则要求前若干条有序路径。它们不再只关心单一最优值，而是关注备选路径集合。此类问题常用于冗余备份、方案比较和搜索拓展。
3.4 网格图与状态图
许多应用场景可转化为网格或状态图，使空间位置与动作规则自然对应到图上的点与边。这样的建模便于统一应用 BFS、Dijkstra 或其扩展版本。
3.4.1 二维网格最短路
二维网格中，每个格子可视为一个点，相邻可走格子之间连边。若每步代价一致，可用 BFS；若不同方向或不同地形代价不同，则常需使用带权最短路。网格模型在迷宫、地图和路径规划中极其常见。
3.4.2 传送门与状态扩展
传送门、开关、钥匙等机制会使“位置”之外还需记录额外状态。此时一个格子可能对应多个状态节点，整个问题被扩展成更大的状态图。虽然规模上升，但能精确表达复杂规则。
3.4.3 迷宫与障碍物模型
迷宫问题通常把障碍物视为不可通过的点或边。最短路求解时，只需在建图阶段屏蔽这些位置即可。若障碍物会移动或出现消失，还需进一步考虑时间维度或动态状态。
4 算法分析
最短路算法的效率分析，通常围绕时间复杂度、空间占用与实现稳定性展开。不同算法在理论最坏情况与实际表现之间，往往存在一定差异。
4.1 时间复杂度
时间复杂度决定了算法能否支撑大规模输入。由于最短路算法种类较多，适用范围也较大，因此需要根据图的稠密程度和权值特征进行选择。
4.1.1 朴素复杂度比较
朴素 Dijkstra 需要线性选点，因此在顶点较多时效率不高；Bellman-Ford 则需要多轮全边扫描，适合边数不大的图；Floyd-Warshall 采用三重循环，复杂度更高，但结构统一，便于处理全源问题。
4.1.2 堆优化复杂度
堆优化 Dijkstra 将选点过程交给优先队列，通常能把单源最短路的效率提升到适合稀疏图的水平。实际复杂度还与堆实现有关，但总体上远优于线性扫描版本。
4.1.3 负权与全源算法复杂度
含负权边的算法通常要经历多轮松弛，因此开销较高。全源算法若直接多次运行单源过程，也会随顶点数成倍增长。选择何种方案，往往取决于图规模、负权存在与否以及查询次数。
4.2 空间复杂度
空间需求主要来自图存储、距离数组、辅助标记与路径记录等部分。对于大图问题，空间管理与时间优化同样重要。
4.2.1 邻接矩阵与邻接表
邻接矩阵适合表示稠密图，查询边是否存在较方便，但占用空间较大。邻接表更适合稀疏图，能够节省存储并提高遍历效率。最短路实现中，邻接表是更常见的选择。
4.2.2 距离数组与辅助数组
距离数组用于保存当前已知最短距离，辅助数组则可能承担访问标记、前驱记录、队列状态等功能。若需要多路径或状态扩展，额外数组数量会明显增加，因此应合理控制维度和初始化成本。
4.3 正确性证明
最短路算法的正确性，通常建立在松弛、贪心和动态规划三种视角之上。不同算法虽然形式各异，但本质上都在维护“当前最优估计并不断改进”的过程。
4.3.1 松弛操作原理
松弛是最短路算法的核心步骤，即尝试用一条经过中间点的路径更新现有距离。只要发现更短的方案，就用新值替换旧值。反复松弛会逐步逼近真实最短距离。
4.3.2 贪心性质与最优子结构
Dijkstra 的正确性依赖非负权图上的贪心性质：当前最小的未确定点，其距离不会再被更短路径改写。与此同时，最短路问题也具有最优子结构，即一条最优路径的任意前缀同样应是相应子问题的最优解。
4.3.3 动态规划视角
Floyd-Warshall 和 Bellman-Ford 可看作动态规划的不同实现方式。它们通过逐步扩大允许使用的中间点数量或边数限制，来系统地更新答案。这种视角有助于理解算法的状态定义与转移逻辑。
4.4 稳定性与实现细节
实际编码时，最短路算法的稳定性常受数据类型、初值设置和边界条件影响。即使理论正确，细节处理不当也可能导致错误结果。
4.4.1 浮点误差问题
若边权为浮点数，比较距离时可能受到精度误差干扰。此时通常需要设置容差，避免因极小差异导致判断不稳定。对于要求严格的场景，整数化建模往往更可靠。
4.4.2 大整数与溢出处理
当路径很长或权值较大时，累计距离可能超过普通整型范围。实现中应选用足够宽的数据类型，并对“无穷大”与加法溢出进行保护，避免错误更新。
4.4.3 初始化与边界条件
距离数组的初始化通常决定算法是否从正确状态开始。起点距离一般设为零，其余点设为无穷大；若有多源，则多个源点同时置零。边界条件还包括空图、单点图、不可达点和自环处理等。
5 路径恢复与输出
最短路算法不仅要给出距离，还常需要输出实际经过的路径。路径恢复依赖额外记录信息，是算法结果展示的重要部分。
5.1 前驱记录
前驱记录用于保存每个点在最优路径上来自哪里。只要有了前驱，就可以从终点一步步回溯到起点，从而重建整条路径。
5.1.1 predecessor 数组
predecessor 数组通常记录某点当前最优路径上的前一个点。每次距离被更新时，同时更新前驱信息。这样做的好处是维护简单，适合大多数单路径输出需求。
5.1.2 路径反向重建
重建路径时，一般从终点开始沿前驱不断回溯，直到到达起点或空标记，再将结果反转即可。若终点不可达，则前驱链通常为空，需在输出阶段单独判断。
5.2 多路径记录
当最短路径不唯一时，仅保存单一前驱不够，需要记录所有可能的最优前驱，以支持多解恢复或统计分析。
5.2.1 记录所有最短前驱
若某点可由多个前驱以相同代价到达，可以把这些前驱都加入记录结构。这样能够保留全部最优转移关系，但会增加空间和输出复杂度，也可能形成大量同价路径分支。
5.2.2 多解输出策略
多解输出时，常见策略包括输出任意一条、输出字典序最小的一条，或枚举若干条代表路径。具体方案取决于题目要求和系统应用目标，不能一概而论。
5.3 结果展示
最短路结果通常包含距离值和对应路径序列两部分。不同场景下，展示方式会有所差异，但核心都是让结果可读、可验证。
5.3.1 路径长度输出
路径长度是最常见的输出内容，通常直接给出最短距离或总代价。若目标点不可达，则输出特殊标记。对于全源问题，可能还需要以矩阵或列表形式展示多个点对结果。
5.3.2 实际路径序列输出
实际路径序列能帮助检查算法正确性，也便于在导航、调度和机器人系统中直接执行。输出时常以顶点编号或坐标序列表示，有时还会附带经过边的信息，以增强可解释性。
6 进阶主题
在基础最短路之外，还存在许多针对复杂状态、动态变化和大规模数据的扩展技术。这些方法常结合搜索、分层建模和启发式策略，提高可用性与灵活性。
6.1 状态最短路
状态最短路把“位置”与“额外属性”共同作为节点的一部分，适用于钥匙、能量、权限或装备等条件参与的路径问题。
6.1.1 位压缩状态图
位压缩常用于表示若干布尔状态，例如已收集的物品集合。每个状态由一个二进制掩码标识，使得状态数可控且便于转移。该方法常见于小规模组合型路径问题。
6.1.2 分层图建模
分层图将不同状态分布到不同层上，再在层间添加转移边。这样可以把复杂约束转化为普通最短路问题。分层结构清晰，适合表达次数限制、权限切换和特殊技能使用等规则。
6.2 动态最短路
动态最短路研究的是图在边权或结构变化后，如何快速更新最短路结果。它比静态问题更接近真实系统，但处理难度也明显更高。
6.2.1 边权修改
当某条边权发生变化时，最短路可能局部或全局受影响。若修改范围较小，可尝试增量更新；若变化较大，则重新计算可能更稳妥。实际采用哪种方式，取决于更新频率与查询成本。
6.2.2 动态插删边
边的插入和删除会改变图结构，进而影响可达性与最短距离。删除操作通常比插入更麻烦，因为它可能使原先的最优路径失效。对此，常需结合数据结构或离线处理技术。
6.2.3 在线查询维护
在线查询要求系统在图持续变化时，仍能快速回答最短路问题。常见思路包括预处理、分块、局部重算和缓存策略。该方向更强调工程可用性，而非单次求解的极限效率。
6.3 启发式搜索
启发式搜索通过引入估价函数，优先扩展更有希望接近目标的节点。它常在大图或目标明确的问题中表现优良。
6.3.1 A* 算法
A* 在已知实际代价和启发式估价的基础上选择扩展顺序。若启发函数满足一定条件，它能够保证找到最优路径，同时在很多实际地图中比盲目搜索更快。
6.3.2 双向搜索
双向搜索从起点和终点同时进行扩展，期望在中间相遇，从而减少搜索范围。它适用于正向和反向都容易展开的问题，尤其在无障碍图或较大网格中较有效。
6.3.3 剪枝策略
剪枝的目的是提前排除明显不可能成为最优解的分支。常见依据包括当前代价上界、启发式下界、重复状态和无效转移等。合理剪枝能显著提高搜索效率，但过强的剪枝也可能误删最优解。
6.4 随机化与近似方法
当图规模极大或要求实时响应时，精确最短路未必总是最合适的选择。此时可以考虑随机化或近似策略，以换取速度和资源上的优势。
6.4.1 近似最短路
近似最短路并不一定给出绝对最优值，但会保证结果在可接受误差范围内。它常用于需要快速响应且对少量误差不敏感的场景，例如大规模推荐、粗粒度规划和快速预估。
6.4.2 大规模图的抽样思想
抽样思想通过只保留部分代表性节点、边或路径信息，来降低计算压力。虽然精度会有所损失，但在超大图中，这种方法能显著减轻内存与时间负担，适合先粗后细的分层处理。
7 应用场景
最短路算法之所以重要，在于它与现实世界的路径优化问题高度对应。无论是交通、通信还是机器人控制，凡涉及“最省”的决策，往往都能找到最短路模型的影子。
7.1 地理与导航
地理信息系统中，路径规划是最短路算法最直观的应用之一。道路、街区和交通规则都可以被抽象为图上的点与边。
7.1.1 路网规划
路网规划主要关注从一个位置到另一个位置的最优通行方案。边权可以表示距离、耗时或收费，不同目标对应不同的最短路定义。实际系统中还会综合道路等级、转向限制和实时交通状况。
7.1.2 实时导航
实时导航需要根据当前位置和即时环境持续更新最优路线。若道路拥堵、封闭或限行，系统需重新评估路径。最短路算法在这里往往与动态数据更新、启发式搜索结合使用。
7.2 网络与通信
在计算机网络中，路由选择本质上也是一种图上的最短路问题。通信链路的代价可能体现为时延、跳数或负载。
7.2.1 路由协议
路由协议常利用最短路径思想决定数据包转发方向。不同协议会采用不同代价定义，有的重视跳数，有的更关心带宽和延迟。最短路模型为这些机制提供了统一的数学基础。
7.2.2 拥塞规避
当网络负载较高时，仅追求最短并不一定最优，因为最短路径可能过于集中，导致拥塞。此时常需在最短路基础上加入负载均衡、容量约束或惩罚项，以获得更稳定的传输效果。
7.3 运筹与物流
物流与运筹问题中，路径优化直接关系到成本、时效和资源利用率。最短路算法能为更复杂的调度模型提供基础子过程。
7.3.1 配送路径规划
配送路径规划要在若干站点之间寻找代价较低的行驶方案。除了距离之外，还可能考虑时间窗、车辆限制和服务顺序。最短路常用于这些模型中的局部连接阶段。
7.3.2 成本最小化模型
在成本最小化问题中，边权可以表示燃料、人工、通行费或综合损耗。通过构造合适的图模型，可以把复杂业务约束转化为可计算的最短路形式，从而支持方案比较和决策分析。
7.4 机器人与游戏
机器人与游戏场景常需要在未知或半已知环境中快速找路。最短路算法在这里不仅影响效率，也影响角色移动的自然程度与智能表现。
7.4.1 机器人寻路
机器人寻路要求在障碍物和传感信息限制下安全到达目标。若环境静态，可直接使用图搜索；若环境会变化，则需结合在线重规划和局部避障策略。最短路常作为全局规划的骨架。
7.4.2 地图 AI 路径决策
游戏中的地图 AI 常借助最短路决定角色巡逻、追击或撤退路线。为了增强表现，开发者有时会在最短路基础上加入随机扰动、行为偏好或区域权重，使移动更符合角色设定。
8 相关概念
最短路算法与图论中的许多基础内容紧密相关。理解这些概念，有助于更全面地把握最短路的理论背景与应用边界。
8.1 图论基础算法
图论中有若干经典算法与最短路并列存在，虽然目标不同，但常在同一工程中配合使用。
8.1.1 最小生成树
最小生成树关注的是用最小总代价连接所有点，而不是某一对点之间的最短路径。它强调全局连通成本，和最短路的“点对点最优”目标不同，但两者都体现了图上的优化思想。
8.1.2 拓扑排序
拓扑排序用于有向无环图中的线性次序安排。对于某些特殊图，最短路可以借助拓扑序进行动态规划式求解，从而比通用算法更高效。
8.2 动态规划与贪心
最短路算法常被视为动态规划和贪心思想在图上的具体体现。不同算法对应不同的状态组织和决策方式。
8.2.1 最优子结构
最优子结构意味着全局最优解可以由子问题最优解组合而成。最短路的这一性质使得局部松弛与分段求解成为可能，也是许多证明的基础。
8.2.2 状态转移
状态转移描述的是从一个已知状态推导到下一个状态的过程。无论是 Bellman-Ford 的边松弛，还是 Floyd-Warshall 的中间点更新，本质上都属于状态转移。
8.3 网络流与匹配
网络流和匹配问题中，最短路经常作为辅助工具参与增广、定价和优化。
8.3.1 与最短增广路的联系
最短增广路是网络流中的一种常见策略，常通过最短路在残量网络中寻找代价较低的增广方向。它将路径优化与流量分配结合起来，是图算法联动的典型例子。
8.3.2 费用流中的最短路思想
费用流问题要求在满足流量约束的同时最小化总费用，因此每一步增广都离不开最短路思想。相关算法会在残量网络上反复寻找最小费用路径，直至达到目标流量。
</INTERNAL_LINK_CANDIDATES> 图论（研究点和边及其关系的数学分支） 广度优先搜索（按层扩展节点的遍历方法） Dijkstra 算法（非负权图单源最短路算法） Bellman-Ford 算法（可处理负权边的单源最短路算法） SPFA 算法（Bellman-Ford 的队列优化版本） Floyd-Warshall 算法（全源最短路动态规划算法） Johnson 算法（处理稀疏图全源最短路的方法） 最小生成树（连接所有节点的最小代价树） 拓扑排序（有向无环图的线性排序方法） 动态规划（通过状态转移求解问题的方法） 贪心算法（每步选择局部最优的策略） A* 算法（带启发式估价的搜索算法） 双向搜索（同时从起点和终点扩展的搜索方法） 网络流（研究图中流量分配的算法体系） 费用流（带边费用约束的流量优化问题）