预备知识

递归及其优化

递归依赖函数调用栈保存每一层执行上下文。基础二分递归在处理状态转移时会生成递归树；由于存在大量重复计算，时间复杂度会呈指数级增长。

1
2
3
4
5
6
7
// 基础递归版本：直接按定义展开 fib(n) = fib(n - 1) + fib(n - 2)。
int fib_recursive (int n) {
    // n 为 0 或 1 时命中递归基，直接返回。
    if (n<=1) return n;
    // 递归求解两个子问题；相同子问题会被重复计算。
    return fib_recursive(n-1) + fib_recursive(n-2);
}

上述代码的空间复杂度受最大调用栈深度限制，通常为 O(n)O(n)；时间复杂度为 O(2n)O(2^n)。基础递归表达直观，但频繁的栈帧分配与销毁会带来较高开销。

尾递归将中间状态作为参数向下传递，使编译器有机会执行尾调用优化。优化后，下层调用可复用当前栈帧，避免调用栈随递归层数增长。

例如，当调用一个 fib_tail_helper(10, 1, 1) 时，这个函数内返回的是递归的 fib_tail_helper(9, 1, 2)，接下来是 fib_tail_helper(8, 2, 3)，以此类推。在不使用尾递归的情况下，在递归调用的函数返回前，都需要保留先前的栈帧，因为递归层数越靠外的函数，返回的就越晚，最终需要的返回值是最外层函数的返回值；而调用尾递归时，实际上并不需要保留之前 10, 1, 1 的参数信息也可以计算出最后的结果，最终需要的返回值在最后一层递归函数返回时就已经得到了，不需要在逐层回到最外层的递归调用，深层的递归函数并不依赖于浅层的递归函数的返回值，因此在有优化的情况下栈帧不会随递归层数增加而增长

1
2
3
4
5
6
7
8
9
10
11
// 尾递归辅助函数：a 保存当前 Fibonacci 值，b 保存下一个 Fibonacci 值。
int fib_tail_helper (int n, int a, int b) {
    // n 归零时，a 即为目标结果。
    if (n==0) return a;
    // 尾调用：下一步状态变为 (n - 1, b, a + b)，当前栈帧不再需要后续计算。
    return fib_tail_helper(n-1, b, a+b);
}
// 对外入口：从 fib(0)=0、fib(1)=1 的初始状态开始递归。
int fib_tail(int n) {
    return fib_tail_helper(n, 0, 1);
}

具备迭代特性的尾递归将时间复杂度降低至 O(n)O(n)，实际空间复杂度取决于编译器是否具备对尾调用优化的底层支持，若支持则可达到 O(1)O(1)。

剥离函数调用栈的约束后，软件工程中最常用的基础版本为纯迭代版本，其状态转换完全在局部变量中通过循环结构进行。迭代和尾递归的思路是类似的：维护和更新两个变量 prev 和 next。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 迭代版本：用两个变量滚动保存相邻两项。
int fib_iter(int n) {
    // fib(0) 的边界情况。
    if (n==0) return 0;
    // a 表示 fib(i - 2)，b 表示 fib(i - 1)。
    int a=0, b=1;
    // 从 fib(2) 开始逐项推进到 fib(n)。
    for (int i=2; i <=n; ++i) {
        // c 是当前要计算的 fib(i)。
        int c=a+b;
        // 窗口右移一位。
        a=b;
        b=c;
    }
    // b 保存循环结束后的 fib(n)。
    return b;
}

从状态转移角度看，此类问题可抽象为动态规划模型。动态规划用显式数据结构保存中间状态，避免重复求解重叠子问题，并通过状态转移方程逐步构造最终解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 动态规划版本：显式保存每个子问题 fib(i) 的结果。
int fib_dp(int n) {
    // 小规模问题直接返回。
    if (n<=1) return n;
    // dp[i] 表示 fib(i)，数组长度为 n + 1。
    vector<int> dp(n+1);
    // 初始条件 fib(0)=0。
    dp[0]=0;
    // 初始条件 fib(1)=1。
    dp[1]=1;
    // 按状态转移方程自底向上填表。
    for (int i=2; i<=n;++i) {
        // fib(i) 只依赖前两项。
        dp[i]=dp[i-1]+dp[i-2];
    }
    // 表中最后一项即为目标结果。
    return dp[n];
}

标准动态规划会开辟长度为 n+1n+1 的数组，空间复杂度为 O(n)O(n)。由于斐波那契数列当前状态只依赖前两个状态，无需维护完整数组。通过滑动窗口只保留必要状态，可将空间复杂度压缩为 O(1)O(1)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 空间优化动态规划：只保留状态转移所需的前两项。
int fib_dp_optimized(int n) {
    // n 为 0 或 1 时不需要进入循环。
    if (n<=1) return n;
    // prev 表示 fib(i - 2)，curr 表示 fib(i - 1)。
    int prev =0, curr =1;
    // 逐步计算 fib(2) 到 fib(n)。
    for (int i=2; i<=n; ++i) {
        // next 是当前 fib(i)。
        int next = prev + curr;
        // 更新窗口，丢弃更早的状态。
        prev = curr;
        curr = next;
    }
    // curr 保存最终的 fib(n)。
    return curr;
}

不同计算范式体现了两类优化：通过状态转移方程消除重复子问题，通过局部变量复用压缩状态空间。这一思路也适用于图论算法优化。

版本 时间复杂度 空间复杂度 备注
递归 O(2n)O(2^n) O(n)O(n) 直观但计算存在大量冗余
尾递归 O(n)O(n) 尾递归优化 O(1)O(1)，否则 O(n)O(n) 递归形式但具备迭代特性
迭代 O(n)O(n) O(1)O(1) 软件开发常规版本
动态规划 O(n)O(n) O(n)O(n) 标准动态规划实现
优化动态规划 O(n)O(n) O(1)O(1) 空间最优的动态规划实现

注：尾递归的实际空间复杂度取决于编译器是否支持尾调用优化。

割集

割集理论是证明多种图上贪心算法正确性的基础。对给定图 G=(V,E)G=(V,E)，若 UU 是顶点集 VV 的非平凡子集，则 UU 与其补集 V∖UV \setminus U 构成一个割，记作 (U:V∖U)(U: V \setminus U)。

任何割都会在网络拓扑中确定一个割集，即跨越该割的边的集合。具体而言，若存在一条边 (u,v)(u, v)，满足其一个端点属于集合 UU 且另一个端点属于补集 V∖UV \setminus U（即 u∈Uu \in U 且 v∈V∖Uv \in V \setminus U），则称该边为跨越边。

割的性质决定了图的连通性约束。在构建支撑树或寻找最短路径时，算法每一步本质上都在评估某个割集的跨越边。贪心策略依据跨越边权重做局部选择，割集理论用于证明该选择可扩展为全局最优解。

最小支撑树

最小支撑树（MST）是网络组合优化的基础模型。对连通网络 N=(V;E)N=(V;E)，子图 T=(V;F)T = (V; F) 若要成为支撑树，必须覆盖所有顶点、保持连通且无环，并满足 ∣V∣=∣F∣+1∣V∣=∣F∣+1。

在树中任意添加一条原本不存在的边必定会产生唯一的一个环；若再删去该同环内的任意一条边，网络即可恢复为树结构。反之，在树中删去任意一条边都会直接破坏网络的全局连通性；再加入一条跨越断开的两个连通分量的边则能再次恢复为完整的树结构。这一性质被称为树的边交换定理，是证明最小支撑树算法正确性的逻辑起点。

同一网络的支撑树通常不唯一。最小支撑树要求在所有支撑树中，边权总和 w(T)=∑e∈Fw(e)w(T) = \sum_{e \in F} w(e) 达到全局最小。

歧义消除

即便网络模型允许权值为零甚至为负数，最小支撑树问题仍然有定义；由于所有合法支撑树所包含的边数必然相等（均为 n−1n-1 条边），因此也可以通过对整个网络的边权值统一加上一个足够大的常数（例如通过 increase(1 - findMin()) 操作）来进行平移调整。这种整体的线性偏移改变了各支撑树总权重的绝对数值，但不会改变不同支撑树之间总权重的相对大小关系，因此不影响最小支撑树的最优解拓扑结构。

当多条边具有相同权值时，同一网络可能存在多棵等权最小支撑树。为保证算法输出确定性，可以引入合成权重机制：将单一边权扩展为三元组 (w(u,v),min⁡(u,v),max⁡(u,v))(w(u, v), \min(u, v), \max(u, v))，并按字典序比较，即 边权重  ⟹  \implies两条边各自较小的点  ⟹  \implies两条边各自较大的点。例如，对于相同权重 5 的边，可通过节点序号排序为 5ab<5ac<5ad<5bc<5bd<5cd5ab < 5ac < 5ad < 5bc < 5bd < 5cd，从而在逻辑上得到唯一确定的最小支撑树。

采用蛮力算法枚举网络 N 的所有可能支撑树并比较其总代价是缺乏计算可行性的。根据图论中的 Cayley 公式，包含 n 个顶点的完全无向图拥有 nn−2n^{n-2} 棵不同的支撑树。这一组合数量级呈现超指数增长特性。

如表所示，当节点数仅为少数时支撑树数量尚在可控范围，但随着节点数目的增加，搜索空间迅速膨胀。鉴于可能的状态空间庞大，现代计算架构必须依赖结构化的图搜索算法而非蛮力枚举来高效逼近解。

优先级搜索

图遍历算法的主要区别在于顶点访问次序不同。广度优先遍历优先访问较早发现的邻接节点，深度优先遍历优先访问较晚发现的纵深节点。访问策略由内部维护可用顶点的数据结构决定。

优先级搜索框架为每个顶点 vv 维护全局优先级 priority(v)，从而将遍历控制流与具体算法策略解耦。顶点在初始化时获得初始优先级，并在算法推进中根据边权信息动态更新。通常优先级数值越大，访问优先级越低；数值越小，访问优先级越高。INT_MAX 表示顶点尚未被触达。

C++ 中利用泛型模板机制构建了高度复用的优先级搜索代码框架。该框架不仅支持顶点类型和边类型的数据抽象，还实现了优先级更新器策略的多态化。全图优先级搜索的入口函数负责扫描全网，确保即使在非连通图的场景下也能覆盖所有孤立分量。

1
2
3
4
5
6
7
8
9
10
11
12
13
// 全图优先级搜索入口；从 s 开始循环扫描所有顶点，覆盖非连通分量。
template <typename Tv, typename Te>
template <typename PU> // PU 是优先级更新策略对象。
void Graph<Tv, Te>::pfs( Rank s, PU prioUpdater ) { // s < n
    // 清空顶点状态、父节点、边类型和优先级等辅助字段。
    reset();
    // 从 s 开始循环 n 次，v % n 用于回绕到编号较小的顶点。
    for ( Rank v = s; v < s + n; v++ )
        // 遇到尚未访问的顶点时，说明发现一个新的连通分量。
        if ( UNDISCOVERED == status( v % n ) )
            // 从该顶点启动单连通分量 PFS。
            PFS( v % n, prioUpdater );
} // 全图每个顶点最终都会被某次 PFS 覆盖。

针对单个连通分量的核心遍历逻辑在 PFS 主函数中展开。算法以起点被标记为已访问状态并设置其优先级为 0 开始，随后进入状态扩张循环。在循环体内，算法首先利用传入的更新器函数对象 prioUpdater 遍历并更新当前顶点所有邻接邻居的优先级及其父节点引用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// 对单个连通分量执行优先级搜索。
template <typename Tv, typename Te>
template <typename PU> // PU 决定 priority 的含义和更新规则。
void Graph<Tv, Te>::PFS( Rank v, PU prioUpdater ) { // 优先级搜索（单个连通域）
    // 起点优先级设为 0，并立即加入搜索树。
    priority( v ) = 0; status( v ) = VISITED;
    // 每轮选择一个当前优先级最高的未访问顶点加入树。
    while ( 1 ) {
        // 以当前顶点 v 为扩展边界，尝试更新所有邻接顶点。
        for ( Rank u = firstNbr( v ); - 1!= u; u = nextNbr( v, u ) )
            // prioUpdater 负责比较并更新 priority(u) 与 parent(u)。
            prioUpdater( this, v, u );
        // shortest 保存当前最小优先级数值。
        int shortest = INT_MAX;
        // 在线性扫描中寻找尚未加入树且 priority 最小的顶点。
        for ( Rank u = 0; u < n; u++ )
            if ( ( UNDISCOVERED == status( u ) ) && ( shortest > priority( u ) ) )
            { shortest = priority( u ), v = u; }
        // 若不存在可达候选顶点，当前连通分量处理完毕。
        if ( shortest == INT_MAX ) break;
        // 将选中的顶点 v 加入树，并把 parent(v)->v 标记为树边。
        status( v ) = VISITED; type( parent( v ), v ) = TREE;
    }
} // 更换 prioUpdater 即可得到 Prim、Dijkstra 等不同算法。

框架时间主要消耗在两类内循环。第一类遍历当前节点邻接顶点并更新优先级，其累计时间依赖图存储结构：邻接矩阵为 O(n2)O(n^2)，邻接表为 O(n+e)O(n+e)。第二类在所有尚未加入树的候选节点中线性扫描最高优先级者，比较次数累计为 O(n2)O(n^2)。因此，不加辅助数据结构时，基础框架整体复杂度为 O(n2)O(n^2)。

若将尚未访问的顶点放入基于堆的优先队列，复杂度会改变：Decrease-Key 累计为 O(elog⁡n)O(e \log n)，Extract-Min 累计为 O(nlog⁡n)O(n \log n)，合计为 O((e+n)log⁡n)O((e+n)\log n)。该优化通常适合稀疏图；对于高密度图，堆调整常数因子和缓存局部性下降可能抵消理论收益。

基于该优先级搜索统一框架，通过定义具体的优先级更新策略，可以派生出各种专业化的拓扑处理算法，最短路径算法即是该框架下的一类典型应用。

PFS 框架中的 priority 不是固定语义，而是一个可被策略函数重新解释的抽象字段。在 Prim 算法中，它通常表示“把该顶点接入当前生成树的最小单边代价”；在 Dijkstra 算法中，它表示“从源点出发到达该顶点的当前最短已知路径长度”。两者控制流相似，但 priority 的含义不同，更新公式也因此不同。

Dijkstra 算法

定义与分类

路径求解可按权重分为无权图搜索模型和带权图数值模型。在带权图中，边权是否全部非负是算法适用性的关键边界。

最短路径问题按计算范围分为单源最短路径和全对最短路径。单源最短路径给定起点 ss，计算从 ss 到其余可达顶点的最短路径和距离。Dijkstra 于 1959 年提出了对应的确定性算法。全对最短路径则求图中任意两点 uu 与 vv 之间的最短路径矩阵，Floyd-Warshall 算法提供了基于动态规划的全局解法。

Dijkstra 算法解决连接节点的两种核心问题：构造网络中所有节点的最小总长度树以及寻找给定两个节点之间的最小长度路径。针对最短路径问题：

  • 将节点集合严格划分为三个动态演化的互斥子集：集合 AA 包含所有已知从原点出发达到最小路径长度的确定节点；集合 BB 包含与集合 AA 中节点邻接但自身尚未被确认最终路径的边缘候选节点；集合 CC 则囊括网络中其余全部尚未被算法波及的节点。

  • 网络中的边被划分为三个对应的集合：集合 II 包含了构成已确认最短路径的内部边；集合 IIII 包含了将集合 AA 连接至集合 BB 的潜在最小边，每一条此类边对应集合 B 中的一个特定节点；集合 IIIIII 包含了剩余未被考察或已被明确拒绝的冗余边。

可以把三个顶点集合看成一条不断外扩的边界。集合 AA 是已经“盖章确认”的区域，集合 BB 是边界上的候选点，集合 CC 是还没有被任何已确认路径触达的远端区域。算法每一轮只做两件事：从 BB 中选出距离最小者并放入 AA，再用它向外更新新的边界。

路径单调性

最短路径算法的贪心选择依赖最短路径的子结构性质：任一全局最短路径的前缀，必定也是起点到该前缀端点的最短路径。

设从网络起点 ss 到终点 vv 的某条最短路径标记为 π(v)\pi(v)。若网络节点 uu 被包含在路径 π(v)\pi(v) 的行进序列上，那么起点 ss 到中间节点 uu 的最短路径 π(u)\pi(u) 必然在拓扑上等价于 π(v)\pi(v) 中从 ss 截取至 uu 的路径段。即只有在 π(u)⊆π(v)\pi(u) \subseteq \pi(v) 的逻辑条件下，最终路径 π(v)\pi(v) 达到全局最短的命题才得以成立。

该结论可用反证法证明。若从 ss 到 uu 存在另一条总代价更小的路径，则可用它替换 π(v)\pi(v) 中从 ss 到 uu 的前缀，并继续沿用原路径从 uu 到 vv 的后缀，从而得到一条到 vv 的更短路径。这与 π(v)\pi(v) 为全局最短路径矛盾。

基于这一定理，从独立起点 ss 出发到达网络中所有其他连通节点的最短路径集合，在将公共前缀进行合并之后，会自然剥离掉图中所有的冗余回路与次优分支，最终形成一种既确保连通又不存在任何环路的树状结构。这棵树包含了起点到达其余所有节点的最短路径方案，被称为最短路径树（SPT）。其数学形式化表达可定义为所有节点最短路径的并集操作：T=Tn−1=⋃0≤i<nπ(ui)\mathcal{T} = \mathcal{T}_{n-1} = \bigcup_{0 \le i < n} \pi(u_i)

需要区分最短路径树与最小支撑树。最小支撑树要求在保证全局连通的前提下，使所选边权总和最小；最短路径树则要求以给定源点为根，使源点到每个节点的路径代价最小。在非对称或权重不均匀的网络中，两者生成的树通常不同。

与最小支撑树类似，最短路径树的结构唯一性依赖权值分布。Dijkstra 算法要求各边权重非负。零权边不会破坏最短路径定义，但可能产生多条等长路径；从源点可达的负权环会使有限最优解不存在。即使负权边不构成负权环，也可能使 Dijkstra 的贪心确定步骤失效。若网络存在大量等效最短路径，可以对原始边权加入极小随机扰动，打破权重对称性并获得确定树结构。

选取与更新状态转换

Dijkstra 算法采用减而治之策略。它维护一个从固定起点出发、逐步向外扩张的最短路径子集。每次迭代确定一个节点的最终距离，缩小未求解节点集合，直到覆盖所有可达节点。

在该渐进式的求解过程中，算法的每一次迭代循环紧密围绕两个核心的执行操作展开：选取（Select）与更新（Update）。

选取操作在每轮前段执行：从尚未纳入最短路径树的候选节点中，选出当前临时距离最小、即优先级数值最小的节点。等价地，在候选集合 BB 中选出最小累积距离节点，并将其转入确定集合 AA。同时，将到达该节点的边从候选边集合 IIII 转入确定树边集合 II。该步骤依赖非负边权：在所有边权非负时，未来绕经其他未确定节点再抵达该节点的路径长度不会变短。因此，当前临时最小距离就是该节点的全局最短距离。

新节点加入最短路径树后，算法执行更新操作。该节点可能为周边未确定节点提供更短路径，因此需要遍历其所有邻接边，对候选或未知邻居进行松弛判断。

设刚被确定的节点为 uku_k，其某个邻接节点为 vv。算法比较 vv 当前已知临时距离与经过 uku_k 到达 vv 的新路径长度。若新路径更短，则更新 vv 的距离，降低其优先级，并将 vv 的父节点指针改为 uku_k。原本距离为无穷的节点若首次获得可行路径，就从隔离集合 CC 转入候选集合 BB。

Dijkstra 的核心不变量是：一旦某个顶点被选中并标记为确定，它的 priority 就再也不会被改小。这个结论依赖非负边权，因为从尚未确定的顶点绕一圈再回来只会让路径长度不减。若允许负边，这个“不回头盖章”的步骤就可能过早。

搜索实例

  • 从点 AA 出发进行搜索，由于其为起点，优先级初始化为 0，加入确定路径节点；
  • 与 AA 邻接的节点 {B(4),D(6),G(7)}\{B(4), D(6), G(7)\} 更新优先级并加入候选边界。BB 的距离最近，加入确定路径节点，踢出候选边界；
  • CC 加入候选边界，候选更新为 {C(16),D(6),G(7)}\{C(16), D(6), G(7)\}。

  • 考察目前候选边界，DD 被加入确定路径节点；
  • 与 DD 邻接的有 {C(15),E(19),G(7)}\{C(15), E(19), G(7)\}，其中 CC 原来就在候选边界中，但是由于找到了更短为 15 的路径更新了优先级，并去除了原来由 AA 经由 BB 到 CC 长度为 16 的路径；另外从 AA 经由 DD 到 GG 的长度为 8 的路径由于劣于之前直接从 AA 到 GG 的长度为 7 的路径，也不再考虑。于是现在候选边界更新为 {C(15),G(7),E(19)}\{C(15), G(7), E(19)\}；
  • 考察目前候选边界，GG 被加入确定路径节点；
  • 与 GG 邻接的有 {E(18),H(21)}\{E(18), H(21)\}，其中 EE 原来就在候选边界中，但是由于找到了更短的路径更新了优先级，并去除了原来由 AA 经由 DD 到 EE 长度为 19 的路径。于是现在候选边界更新为 {C(15),E(18),H(21)}\{C(15), E(18), H(21)\}。

  • 考察目前候选边界，CC 被加入确定路径节点；
  • 与 CC 邻接的有 {E(16),F(17)}\{E(16), F(17)\}，其中 EE 原来就在候选边界中，但是由于找到了更短为 16 的路径更新了优先级，并去除了原来由 AA 经由 GG 到 EE 长度为 18 的路径；另外从 AA 经由 DD 到 CC 到 HH 的长度为 25 的路径由于劣于之前直接从 AA 到 GG 到 HH 的长度为 21 的路径，也不再考虑。于是现在候选边界更新为 {E(16),F(17),H(21)}\{E(16), F(17), H(21)\}；
  • 考察目前候选边界，EE 被加入确定路径节点；
  • 与之前同理，采用总路程更短的路径并去除次优路径，候选边界更新为 {F(17),H(21)}\{F(17), H(21)\}。

  • 考察目前候选边界，FF 被加入确定路径节点；
  • 从 FF 到 HH 路径更优，候选边界更新为 {H(20)}\{H(20)\}，最后 HH 加入，搜索结束，得到一棵由 AA 出发到所有点都最近的最短路径树。

PrioUpdater() 实现

针对任意节点集合 VkV_k​外的一切游离节点，算法初始化将其优先级值设定为无限大（∞∞）。随后直接套用优先级搜索统一框架，为了使已形成的最短路径树 TkT_k​向外扩充一个节点至 Tk+1T_{k+1} 状态，仅需选出优先级数值最小（即距离起点最近）的跨界边及其对应的顶点 uku_k，并将其并入确定的树结构中。随后，遍历并更新剩余未覆盖集合 V∖Vk+1V \setminus V_{k+1} 中所有相关顶点的优先级。那些在这一轮中优先级可能出现实质性降低的顶点，必定与刚刚加入树的边界节点 uku_k 存在物理上的邻接关系。

因此，核心操作是枚举 uku_k 的所有邻接顶点，并按下式更新优先级：

priority(v)=min⁡(priority(v),priority(uk)+w(uk,v))\text{priority}(v) = \min(\text{priority}(v), \text{priority}(u_k) + w(u_k, v))

具体实现中，该更新策略封装在 DijkPU 中：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// Dijkstra 的优先级更新器：priority(u) 表示源点到 u 的当前最短已知距离。
template <typename Tv, typename Te> struct DijkPU {
    // v 是刚加入最短路径树的顶点，u 是 v 的邻接顶点。
    virtual void operator()( Graph<Tv, Te>* g, Rank v, Rank u ) {
        // 只松弛尚未被纳入最短路径树的顶点，已确定顶点的距离不再回退。
        if ( UNDISCOVERED == g->status( u ) )
            // 若经过 v 到达 u 的新路径更短，则执行松弛。
            if ( g->priority( u ) > g->priority( v ) + g->weight( v, u ) ) {
                // 更新源点到 u 的临时最短距离。
                g->priority( u ) = g->priority( v ) + g->weight( v, u );
                // 记录当前最优路径上 u 的前驱顶点。
                g->parent( u ) = v;
            }
    }
};

条件判断 g->priority(u) > g->priority(v) + g->weight(v, u) 比较了目标节点 u 的当前已知最短距离与经过中间节点 v 中转到达 u 的新组合距离。若中转路径能够压缩累积距离，系统便会将 u 的先驱父节点重新定向为 v，并同步更新优先队列中的权重标识。

针对一般有向图进行计算的模块 graph_dijkstra.h ：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
// 以 s 为源点计算单源最短路径；要求所有边权非负。
template <typename Tv, typename Te>
void Graph<Tv, Te>::dijkstra( Rank s ) { // s < n
    // 初始化所有顶点状态和优先级。
    reset();
    // 源点到自身距离为 0，其余顶点保持 INT_MAX。
    priority( s ) = 0;
    // 每轮确定一个当前临时距离最小的顶点。
    for ( Rank i = 0; i < n; i++ ) {
        // 当前 s 的最短距离已经确定，加入最短路径树。
        status( s ) = VISITED;
        // 非源点加入树时，把其父边标记为树边。
        if ( -1!= parent( s ) ) type( parent( s ), s ) = TREE;
        // 枚举 s 的所有邻接顶点 j。
        for ( Rank j = firstNbr( s ); - 1!= j; j = nextNbr( s, j ) )
            // 只对未确定顶点执行松弛。
            if ( ( status( j ) == UNDISCOVERED ) && ( priority( j ) > priority( s ) + weight( s, j ) ) )
            {
                // 经过 s 到达 j 的路径更短，更新距离与前驱。
                priority( j ) = priority( s ) + weight( s, j ); parent( j ) = s;
            }
        // shortest 保存下一轮候选顶点中的最小临时距离。
        int shortest = INT_MAX;
        // 线性扫描所有未确定顶点，选出下一最近顶点。
        for ( Rank j = 0; j < n; j++ )
            if ( ( status( j ) == UNDISCOVERED ) && ( shortest > priority( j ) ) )
            { shortest = priority( j ); s = j; }
        // 剩余未确定顶点均不可达时提前停止。
        if ( shortest == INT_MAX ) break;
    }
} // 无向图可表示为两条方向相反且权重相等的有向边。

对比该实现与求解最小支撑树的 Prim 算法实现：Prim 算法在权衡节点引入成本时，仅考量孤立节点接入当前支撑树的最短单一边权值；而 Dijkstra 算法在此基础上引入了历史状态的累加，综合考量从起始节点至目标节点所在末端的累积路径权值总和。

总的来说，Prim 关心“接进树的这条边便宜不便宜”，Dijkstra 关心“从源点走到这里的整条路短不短”。所以 Prim 的更新公式只看 weight(v,u)，而 Dijkstra 的更新公式要看 priority(v) + weight(v,u)。

负权边边界

Dijkstra 算法要求所有边权非负。若图中存在负权边，路径代价单调累积假设会被破坏，算法的贪心确定步骤可能失效。

负权边会打破路径生长的单调性。一条当前较长而暂未被选中的路径，后续可能经过负权边使总长度下降，从而更新已经被 Dijkstra 判定为“确定最短”的节点。若存在从源点可达的负权环，路径可以反复绕环使总代价趋向负无穷，此时有限最短路径本身不存在。

对于含负权边但无负权环的单源最短路径问题，Bellman-Ford 及其优化形式 SPFA 是常见方案。这类算法不依赖局部贪心确定，而是对全体边进行多轮松弛，并在末期检测负权环。

针对规模受限但要求全量两两节点最短路径矩阵的需求，Floyd-Warshall 算法通过三重嵌套循环的动态规划状态转移方程，在处理高密度网络互联时规避了针对不同拓扑起点的重复拓扑解析，是构建大规模骨干网多源路由表信息的常规选择。

在二维地图导航、机器人路径规划等具有空间坐标的场景中，仅依赖边权进行无启发式搜索可能产生较多无效扩展。A*（A-Star）通过引入启发式估价函数，将已累计距离与到目标的估计距离结合，引导搜索向目标区域推进。

相关可以参考 CS188：
Uniform Cost 搜索：Uniformed Search
启发式搜索和 A* 算法：Informed Search