Algorithms_4th学习:有向无环图（DAG）上的最短路径与最长路径

虾球xz

141人浏览 · 2026-04-06 12:17:00

虾球xz · 2026-04-06 12:17:00 发布

一、为什么 DAG 能做得更好？

前面的 Dijkstra 算法有两个限制：

需要优先队列，时间复杂度 $\log V)$
边权不能为负
对于有向无环图（DAG，Directed Acyclic Graph），有一种更快的方法：

按拓扑顺序逐一松弛顶点，只需 $O (E + V)$ 的线性时间，而且允许负权边。
优势总结：

特性	Dijkstra	DAG 拓扑排序法
时间复杂度	$\log V)$	$O (E + V)$
允许负权边	否	是
要求无环	否	是（DAG 专用）
能求最长路径	否	是（取反即可）

二、核心思想：拓扑顺序松弛

拓扑顺序的关键性质：

若边 $\to w$ 存在，则 $v$ 在拓扑序中一定排在 $w$ 前面。
这意味着：当我们处理顶点 $v$ 时，所有"能影响 $d i s tT o [v]$ "的顶点都已经处理完了。
因此松弛顶点 $v$ 之后， $d i s tT o [v]$ 就再也不会被更新了——无需优先队列，从前往后线性扫一遍即可。

拓扑顺序保证：
  处理顶点 v 时：
    所有指向 v 的边 u->v，u 均已被处理
    => distTo[v] 此时已是最终值，永不再变
    => 可以安全地松弛 v 的所有出边

三、命题 S：DAG 最短路径线性时间

命题 S： 对带权 DAG，按拓扑顺序松弛顶点，可在 $O (E + V)$ 时间内求解单源最短路径。
证明：

每条边 $\to w$ 恰好被松弛一次（当 $v$ 被处理时）
松弛后： $\leq distTo[v] + weight(v \to w)$
由于是拓扑顺序， $v$ 处理后不会再有边指向 $v$ ，所以 $d i s tT o [v]$ 不会再变小
$d i s tT o [w]$ 只能减小（松弛只减不增）
因此该不等式在算法结束前始终成立
算法结束时最优性条件（命题 P）满足， $d i s tT o []$ 即为最短路径
时间分析：
$\underbrace{O(E + V)}_{\text{拓扑排序（DFS）}} + \underbrace{O(E + V)}_{\text{按拓扑序松弛每条边一次}} = O(E + V)$

四、拓扑排序回顾（DFS 后序逆置）

拓扑排序基于 DFS：

DFS(v):
  标记 v 为已访问
  对 v 的每条出边 v->w:
      若 w 未访问，递归 DFS(w)
  将 v 压入栈
DFS 全部完成后，弹出栈即为拓扑顺序。

对 tinyEWDAG 从顶点 5 出发，DFS 得到拓扑顺序：
$\to 1 \to 3 \to 6 \to 4 \to 7 \to 0 \to 2$

五、算法执行追踪（tinyEWDAG，源点 5）

图的边（tinyEWDAG）：

5->4(0.35)  5->1(0.32)  5->7(0.28)
4->0(0.38)  4->7(0.34)
1->3(0.29)
3->6(0.52)  3->7(0.37)
6->4(0.93)  6->0(0.58)  6->2(0.40)
7->2(0.34)
0->2(0.26)

按拓扑顺序 5→1→3→6→4→7→0→2 依次松弛：

初始：
  distTo = [INF, INF, INF, INF, INF, 0.00, INF, INF]
                                       ^5
处理 5（distTo=0.00），松弛出边：
  5->4: distTo[4] = 0.00+0.35 = 0.35  edgeTo[4]=5->4
  5->1: distTo[1] = 0.00+0.32 = 0.32  edgeTo[1]=5->1
  5->7: distTo[7] = 0.00+0.28 = 0.28  edgeTo[7]=5->7
  distTo = [INF, 0.32, INF, INF, 0.35, 0.00, INF, 0.28]
处理 1（distTo=0.32），松弛出边：
  1->3: distTo[3] = 0.32+0.29 = 0.61  edgeTo[3]=1->3
  distTo = [INF, 0.32, INF, 0.61, 0.35, 0.00, INF, 0.28]
处理 3（distTo=0.61），松弛出边：
  3->6: distTo[6] = 0.61+0.52 = 1.13  edgeTo[6]=3->6
  3->7: 0.61+0.37=0.98 > 0.28，不更新（不可用）
  distTo = [INF, 0.32, INF, 0.61, 0.35, 0.00, 1.13, 0.28]
处理 6（distTo=1.13），松弛出边：
  6->4: 1.13+0.93=2.06 > 0.35，不更新
  6->0: distTo[0] = 1.13+0.58 = 1.71  edgeTo[0]=6->0
  6->2: distTo[2] = 1.13+0.40 = 1.53  edgeTo[2]=6->2
  distTo = [1.71, 0.32, 1.53, 0.61, 0.35, 0.00, 1.13, 0.28]
处理 4（distTo=0.35），松弛出边：
  4->0: 0.35+0.38=0.73 < 1.71，更新！  edgeTo[0]=4->0
  4->7: 0.35+0.34=0.69 > 0.28，不更新
  distTo = [0.73, 0.32, 1.53, 0.61, 0.35, 0.00, 1.13, 0.28]
处理 7（distTo=0.28），松弛出边：
  7->2: 0.28+0.34=0.62 < 1.53，更新！  edgeTo[2]=7->2
  distTo = [0.73, 0.32, 0.62, 0.61, 0.35, 0.00, 1.13, 0.28]
处理 0（distTo=0.73），松弛出边：
  0->2: 0.73+0.26=0.99 > 0.62，不更新
处理 2（distTo=0.62），无出边。
最终：
  distTo = [0.73, 0.32, 0.62, 0.61, 0.35, 0.00, 1.13, 0.28]

最终最短路径树（SPT，源点 5）：

六、最长路径：取反转化

命题 T： DAG 上的最长路径问题可在 $O (E + V)$ 时间内求解。
转化方法：

将图中所有边的权重取反，然后在新图上求最短路径，最后将结果再取反，即为原图的最长路径。
$最长路径(G)=−最短路径(−G)\text{最长路径}(G) = -\text{最短路径}(-G)$
或者，更简单的实现方式：

初始化 $-\infty$ （除源点外）
松弛条件改为：若 $d i s tT o [v] + w e i g h t > d i s tT o [w]$ ，则更新（取最大值而非最小值）

最短路径 relax：            最长路径 relax：
if (newDist < distTo[w])   if (newDist > distTo[w])
    更新                        更新

最长路径执行追踪（tinyEWDAG，源点 5）：

拓扑顺序：5→1→3→6→4→7→0→2（与最短路径相同）
初始：distTo = [-INF,-INF,-INF,-INF,-INF, 0.00,-INF,-INF]
处理 5：distTo[4]=0.35, distTo[1]=0.32, distTo[7]=0.28
处理 1：distTo[3] = 0.32+0.29 = 0.61
处理 3：distTo[6] = 0.61+0.52 = 1.13
        distTo[7] = max(0.28, 0.61+0.37) = max(0.28, 0.98) = 0.98（更新！）
处理 6：distTo[4] = max(0.35, 1.13+0.93) = max(0.35, 2.06) = 2.06（更新！）
        distTo[0] = max(-INF, 1.13+0.58) = 1.71
        distTo[2] = max(-INF, 1.13+0.40) = 1.53
处理 4：distTo[0] = max(1.71, 2.06+0.38) = max(1.71, 2.44) = 2.44（更新！）
        distTo[7] = max(0.98, 2.06+0.34) = max(0.98, 2.40) = 2.40（更新！）
处理 7：distTo[2] = max(1.53, 2.40+0.34) = max(1.53, 2.74) = 2.74（更新！）
处理 0：distTo[2] = max(2.74, 2.44+0.26) = max(2.74, 2.70) = 2.74（不更新）
最终最长距离：
  distTo = [2.44, 0.32, 2.74, 0.61, 2.06, 0.00, 1.13, 2.40]

最终最长路径树（LPT，源点 5）：

与普通图的对比（为何 DAG 上最长路径高效而一般图不行）：

一般有向图（含环）上的最长路径 = NP 难问题，已知最优算法需指数时间
DAG（无环）上的最长路径       = 线性时间 O(E+V)，转化为最短路径即可
"环的存在"让最长路径问题变得指数级困难。

七、C++ 完整实现

#include <iostream>
#include <vector>
#include <stack>
#include <limits>
#include <iomanip>
#include <string>
#include <sstream>
// ============================================================
// 带权有向边
// ============================================================
class DirectedEdge {
    int    v_, w_;
    double wt_;
public:
    DirectedEdge(int v, int w, double wt) : v_(v), w_(w), wt_(wt) {}
    int    from()   const { return v_;  }
    int    to()     const { return w_;  }
    double weight() const { return wt_; }
    std::string str() const {
        std::ostringstream o;
        o << v_ << "->" << w_ << " "
          << std::fixed << std::setprecision(2) << wt_;
        return o.str();
    }
};
// ============================================================
// 带权有向图（邻接表）
// ============================================================
class EdgeWeightedDigraph {
    int V_, E_;
    std::vector<std::vector<DirectedEdge>> adj_;
public:
    explicit EdgeWeightedDigraph(int V) : V_(V), E_(0), adj_(V) {}
    int V() const { return V_; }
    int E() const { return E_; }
    void addEdge(const DirectedEdge& e) {
        adj_[e.from()].push_back(e);
        ++E_;
    }
    const std::vector<DirectedEdge>& adj(int v) const { return adj_[v]; }
};
// ============================================================
// 拓扑排序（基于 DFS 后序逆置）
// 仅适用于 DAG，若图含环则结果无意义
// ============================================================
class Topological {
    std::vector<bool> visited_;  // 标记顶点是否已访问
    std::vector<int>  order_;    // 拓扑顺序（从前到后）
    // DFS：递归访问 v 的所有后继，最后将 v 压栈
    void dfs(const EdgeWeightedDigraph& G, int v,
             std::stack<int>& stk)
    {
        visited_[v] = true;
        for (const auto& e : G.adj(v)) {
            int w = e.to();
            if (!visited_[w])
                dfs(G, w, stk);
        }
        // 后序：v 的所有后继都处理完后，才把 v 入栈
        stk.push(v);
    }
public:
    explicit Topological(const EdgeWeightedDigraph& G)
        : visited_(G.V(), false)
    {
        std::stack<int> stk;
        // 对所有未访问的顶点启动 DFS（处理不连通情况）
        for (int v = 0; v < G.V(); v++)
            if (!visited_[v])
                dfs(G, v, stk);
        // 弹栈得到拓扑顺序（后序逆置 = 拓扑序）
        while (!stk.empty()) {
            order_.push_back(stk.top());
            stk.pop();
        }
    }
    // 返回拓扑顺序
    const std::vector<int>& order() const { return order_; }
};
// ============================================================
// DAG 最短路径（AcyclicSP）
//
// 算法步骤：
//   1. 对图做拓扑排序，得到顶点处理顺序
//   2. 按拓扑顺序逐一松弛每个顶点的所有出边
//
// 时间复杂度 O(E+V)，允许负权边，要求无环
// ============================================================
class AcyclicSP {
    static constexpr double INF = std::numeric_limits<double>::infinity();
    std::vector<double> distTo_;  // distTo_[v]: s 到 v 的最短距离
    std::vector<int>    prevV_;   // prevV_[v]:  最短路径上 v 的父顶点
    std::vector<double> prevWt_;  // prevWt_[v]: 父边权重
    // 松弛顶点 v 的所有出边
    // 若经由 v 能缩短到某后继顶点的距离，则更新
    void relax(const EdgeWeightedDigraph& G, int v) {
        for (const auto& e : G.adj(v)) {
            int    w    = e.to();
            double newD = distTo_[v] + e.weight();
            // 最短路径：取更小值
            if (newD < distTo_[w]) {
                distTo_[w] = newD;
                prevV_[w]  = v;
                prevWt_[w] = e.weight();
            }
        }
    }
public:
    AcyclicSP(const EdgeWeightedDigraph& G, int s)
        : distTo_(G.V(), INF),
          prevV_(G.V(), -1),
          prevWt_(G.V(), 0.0)
    {
        distTo_[s] = 0.0;
        // 第一步：拓扑排序
        Topological topo(G);
        // 第二步：按拓扑顺序松弛
        // 由于拓扑顺序保证"v 的所有前驱都已处理"，
        // 松弛 v 时 distTo_[v] 已是最终最短值
        for (int v : topo.order())
            relax(G, v);
    }
    double distTo(int v)  const { return distTo_[v]; }
    bool hasPathTo(int v) const { return distTo_[v] < INF; }
    // 回溯 prevV_[] 构建路径
    std::vector<std::pair<int,int>> pathTo(int v) const {
        if (!hasPathTo(v)) return {};
        std::stack<std::pair<int,int>> stk;
        for (int cur = v; prevV_[cur] != -1; cur = prevV_[cur])
            stk.push({prevV_[cur], cur});
        std::vector<std::pair<int,int>> path;
        while (!stk.empty()) { path.push_back(stk.top()); stk.pop(); }
        return path;
    }
};
// ============================================================
// DAG 最长路径（AcyclicLP）
//
// 与 AcyclicSP 的唯一区别：
//   - distTo_ 初始化为 -INF（而非 +INF）
//   - relax 条件改为 newD > distTo_[w]（取更大值）
//
// 等价于对所有边权取反后求最短路径，再将结果取反
// ============================================================
class AcyclicLP {
    static constexpr double NEG_INF = -std::numeric_limits<double>::infinity();
    std::vector<double> distTo_;
    std::vector<int>    prevV_;
    std::vector<double> prevWt_;
    // 松弛（最长路径版）：取更大值
    void relax(const EdgeWeightedDigraph& G, int v) {
        for (const auto& e : G.adj(v)) {
            int    w    = e.to();
            double newD = distTo_[v] + e.weight();
            // 最长路径：取更大值（与最短路径的唯一区别）
            if (newD > distTo_[w]) {
                distTo_[w] = newD;
                prevV_[w]  = v;
                prevWt_[w] = e.weight();
            }
        }
    }
public:
    AcyclicLP(const EdgeWeightedDigraph& G, int s)
        : distTo_(G.V(), NEG_INF),
          prevV_(G.V(), -1),
          prevWt_(G.V(), 0.0)
    {
        distTo_[s] = 0.0;
        Topological topo(G);
        for (int v : topo.order())
            relax(G, v);
    }
    double distTo(int v)  const { return distTo_[v]; }
    bool hasPathTo(int v) const {
        return distTo_[v] > -std::numeric_limits<double>::infinity();
    }
    std::vector<std::pair<int,int>> pathTo(int v) const {
        if (!hasPathTo(v)) return {};
        std::stack<std::pair<int,int>> stk;
        for (int cur = v; prevV_[cur] != -1; cur = prevV_[cur])
            stk.push({prevV_[cur], cur});
        std::vector<std::pair<int,int>> path;
        while (!stk.empty()) { path.push_back(stk.top()); stk.pop(); }
        return path;
    }
};
// ============================================================
// 打印路径工具函数
// ============================================================
void printPaths(const std::string& title, int src, int V,
                const AcyclicSP& sp)
{
    std::cout << title << "\n";
    std::cout << std::string(55, '-') << "\n";
    for (int t = 0; t < V; t++) {
        std::cout << src << " -> " << t
                  << std::fixed << std::setprecision(2)
                  << "  (" << sp.distTo(t) << ")  ";
        if (sp.hasPathTo(t))
            for (auto [u, v] : sp.pathTo(t))
                std::cout << u << "->" << v << "  ";
        else
            std::cout << "不可达";
        std::cout << "\n";
    }
    std::cout << "\n";
}
void printPathsLP(const std::string& title, int src, int V,
                  const AcyclicLP& lp)
{
    std::cout << title << "\n";
    std::cout << std::string(55, '-') << "\n";
    for (int t = 0; t < V; t++) {
        std::cout << src << " -> " << t
                  << std::fixed << std::setprecision(2)
                  << "  (" << lp.distTo(t) << ")  ";
        if (lp.hasPathTo(t))
            for (auto [u, v] : lp.pathTo(t))
                std::cout << u << "->" << v << "  ";
        else
            std::cout << "不可达";
        std::cout << "\n";
    }
    std::cout << "\n";
}
// ============================================================
// 主程序：tinyEWDAG，源点 5
// ============================================================
int main() {
    // 构造 tinyEWDAG（8 顶点）
    EdgeWeightedDigraph G(8);
    G.addEdge({5, 4, 0.35}); G.addEdge({5, 1, 0.32}); G.addEdge({5, 7, 0.28});
    G.addEdge({4, 0, 0.38}); G.addEdge({4, 7, 0.34});
    G.addEdge({1, 3, 0.29});
    G.addEdge({3, 6, 0.52}); G.addEdge({3, 7, 0.37});
    G.addEdge({6, 4, 0.93}); G.addEdge({6, 0, 0.58}); G.addEdge({6, 2, 0.40});
    G.addEdge({7, 2, 0.34});
    G.addEdge({0, 2, 0.26});
    int s = 5;
    // 打印拓扑顺序
    Topological topo(G);
    std::cout << "拓扑顺序: ";
    for (int v : topo.order()) std::cout << v << " ";
    std::cout << "\n\n";
    // 最短路径
    AcyclicSP sp(G, s);
    printPaths("=== DAG 最短路径（源点 5）===", s, G.V(), sp);
    // 最长路径
    AcyclicLP lp(G, s);
    printPathsLP("=== DAG 最长路径（源点 5）===", s, G.V(), lp);
    return 0;
}

八、算法对比总览

九、预期输出

拓扑顺序: 5 1 3 6 4 7 0 2
=== DAG 最短路径（源点 5）===
-------------------------------------------------------
5 -> 0  (0.73)  5->4  4->0
5 -> 1  (0.32)  5->1
5 -> 2  (0.62)  5->7  7->2
5 -> 3  (0.61)  5->1  1->3
5 -> 4  (0.35)  5->4
5 -> 5  (0.00)
5 -> 6  (1.13)  5->1  1->3  3->6
5 -> 7  (0.28)  5->7
=== DAG 最长路径（源点 5）===
-------------------------------------------------------
5 -> 0  (2.44)  5->1  1->3  3->6  6->4  4->0
5 -> 1  (0.32)  5->1
5 -> 2  (2.74)  5->1  1->3  3->6  6->4  4->7  7->2
5 -> 3  (0.61)  5->1  1->3
5 -> 4  (2.06)  5->1  1->3  3->6  6->4
5 -> 5  (0.00)
5 -> 6  (1.13)  5->1  1->3  3->6
5 -> 7  (2.40)  5->1  1->3  3->6  6->4  4->7

十、关键点总结

拓扑顺序是关键：DAG 上按拓扑顺序松弛，保证处理 $v$ 时 $d i s tT o [v]$ 已是最终值，无需优先队列。
线性时间 $O (E + V)$ ：拓扑排序一遍，松弛一遍，每条边恰好被处理一次。
允许负权边：证明不依赖边权非负，只依赖拓扑顺序的单向传播性。
最长路径只需两处修改：初始化从 $+∞+\infty$ 改为 $−∞-\infty$ ，松弛判断从 $<$ 改为 $>$ 。
无环是前提：若图含环，拓扑排序无法进行，需改用 Bellman-Ford 算法。对一般有向图（含环）求最长路径是 NP 难问题。

并行任务调度与关键路径法（CPM）

基于《算法（第4版）》4.4节，改写为 C++ 视角，配有详细中文解析与完整可运行代码。

一、问题描述

什么是并行任务调度？

想象你在建一栋楼：

打地基 → 必须先于盖墙
盖墙 → 必须先于装窗户
但"装水管"和"装电线"可以同时进行（只要前置任务完成）
目标：用尽可能多的处理器（工人），在满足所有前置约束的前提下，最短时间内完成所有任务。

问题的本质

这个问题等价于：在一个带权有向无环图（DAG）中，求最长路径。
这个技术叫做 关键路径法（Critical Path Method，CPM），广泛用于工程项目管理。

二、样例问题

任务编号	持续时间	必须在此之前完成
0	41.0	1, 7, 9
1	51.0	2
2	50.0	—
3	36.0	—
4	38.0	—
5	45.0	—
6	21.0	3, 8
7	32.0	3, 8
8	32.0	2
9	29.0	4, 6

最优调度结果（最短完工时间 = 173.0）：

时间轴:
0   ----[任务0: 41]----
0   ----[任务5: 45]----
41  --------[任务1: 51]--------
41  --[任务7: 32]--
41  --[任务9: 29]--
70  ---[任务4: 38]---
70  --[任务6: 21]--
91  ----[任务3: 36]----
91  ----[任务8: 32]----
123 -----------[任务2: 50]----------- (结束于173)

三、关键路径是什么？

关键路径是所有约束链中最长的那条。
在本例中：

任务0(41) → 任务9(29) → 任务6(21) → 任务8(32) → 任务2(50)
总长度 = 41 + 29 + 21 + 32 + 50 = 173

这条链上的任何一个任务延迟，整个项目就会延迟。这就是"关键"的含义。

任何一组有序任务链的总时长，都是整体完工时间的下界。
其中最长的那条链，就是完工时间的精确下界（同时也是上界），因此关键路径长度 = 最优完工时间。

四、建图方法：把调度问题变成最长路径问题

图的构造规则

对于 $N$ 个任务，我们构造一个带权 DAG，共 $2 N + 2$ 个顶点：

顶点 $i$ ：任务 $i$ 的开始节点（ $\le i < N$ ）
顶点 $i + N$ ：任务 $i$ 的结束节点
顶点 $s = 2 N$ ：超级源点
顶点 $t = 2 N + 1$ ：超级汇点
三类边：
| 边的类型 | 起点 | 终点 | 权重 |
|:—😐:—😐:—😐:—😐
| 任务本身 | $i$ （开始） | $i + N$ （结束） | 任务持续时间 |
| 前置约束 $\to j$ | $i + N$ （ $i$ 的结束） | $j$ （ $j$ 的开始） | $0$ |
| 源点到每个任务 | $s$ | $i$ （开始） | $0$ |
| 每个任务到汇点 | $i + N$ （结束） | $t$ | $0$ |

为什么这样建图有效？

从 $s$ 到任务 $i$ 开始节点的最长路径，就是任务 $i$ 最早能开始的时间。
因为路径上每经过一段"任务"，都要加上它的持续时间；经过"约束"边，不加时间但保证顺序。
从 $s$ 到 $t$ 的最长路径 = 整个项目的最短完工时间。

图示（本例 DAG）

                   41
        s ---0→[任务0开始]---→[任务0结束]---0→ 1(开始)
        |                       |  0→ 7(开始)
        |                       |  0→ 9(开始)
        |      51               ↓
        s ---0→[任务1开始]---→[任务1结束]---0→ 2(开始)
        |      ...             ...
        |                       ↓
        s ---0→ ... ---→ ... ---0→ t

五、Mermaid 图示：DAG 结构

六、算法流程

在 DAG 上求最长路径，使用拓扑排序 + 动态规划（也叫 AcyclicLP 算法）：
$\text{distTo}[v] = \max_{(u,v) \in E} \left( \text{distTo}[u] + w(u,v) \right)$
即：到达顶点 $v$ 的最长距离 = 所有前驱节点 $u$ 的最长距离 + 对应边权的最大值。
算法步骤：

对图进行拓扑排序
按拓扑顺序逐个松弛每条边（取最大值而不是最小值）
distTo[i] 即为任务 $i$ 的最早开始时间
distTo[t] 即为最短完工时间

七、完整 C++ 实现

#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <limits>
#include <string>
#include <sstream>
// ============================================================
// 有向加权边
// ============================================================
struct DirectedEdge {
    int from;    // 起点
    int to;      // 终点
    double weight; // 边权（任务持续时间 或 0）
    DirectedEdge(int u, int v, double w) : from(u), to(v), weight(w) {}
};
// ============================================================
// 有向加权图（邻接表）
// ============================================================
class EdgeWeightedDigraph {
public:
    int V; // 顶点数
    std::vector<std::vector<DirectedEdge>> adj; // 邻接表
    EdgeWeightedDigraph(int v) : V(v), adj(v) {}
    // 添加一条有向边
    void addEdge(const DirectedEdge& e) {
        adj[e.from].push_back(e);
    }
};
// ============================================================
// 拓扑排序（基于 DFS）
// ============================================================
class TopologicalSort {
public:
    std::vector<bool> visited;
    std::stack<int> reversePost; // 逆后序 = 拓扑序
    TopologicalSort(const EdgeWeightedDigraph& G) : visited(G.V, false) {
        for (int v = 0; v < G.V; v++) {
            if (!visited[v]) dfs(G, v);
        }
    }
    void dfs(const EdgeWeightedDigraph& G, int v) {
        visited[v] = true;
        for (const auto& e : G.adj[v]) {
            if (!visited[e.to]) dfs(G, e.to);
        }
        reversePost.push(v); // 后序：所有邻居访问完后入栈
    }
    // 返回拓扑顺序
    std::vector<int> order() {
        std::vector<int> result;
        std::stack<int> tmp = reversePost;
        while (!tmp.empty()) {
            result.push_back(tmp.top());
            tmp.pop();
        }
        return result;
    }
};
// ============================================================
// DAG 最长路径算法（AcyclicLP）
// ============================================================
class AcyclicLP {
public:
    std::vector<double> distTo;   // distTo[v] = 从源点到 v 的最长距离
    std::vector<int> edgeTo;      // edgeTo[v] = 到达 v 的最后一条边的起点（用于回溯路径）
    AcyclicLP(const EdgeWeightedDigraph& G, int s) 
        : distTo(G.V, -std::numeric_limits<double>::infinity()), 
          edgeTo(G.V, -1) 
    {
        distTo[s] = 0.0; // 源点到自身距离为 0
        // 拓扑排序
        TopologicalSort topo(G);
        std::vector<int> order = topo.order();
        // 按拓扑顺序松弛每个顶点的所有出边
        for (int v : order) {
            // 如果 v 还没被源点可达，跳过
            if (distTo[v] == -std::numeric_limits<double>::infinity()) continue;
            for (const auto& e : G.adj[v]) {
                // 松弛操作：若经过 v 能到达 e.to 且路径更长，则更新
                if (distTo[e.to] < distTo[v] + e.weight) {
                    distTo[e.to] = distTo[v] + e.weight;
                    edgeTo[e.to] = v; // 记录前驱，用于回溯关键路径
                }
            }
        }
    }
};
// ============================================================
// 解析一行输入：格式为 "持续时间 [后继任务1 后继任务2 ...]"
// ============================================================
struct JobInfo {
    double duration;
    std::vector<int> successors;
};
JobInfo parseJobLine(const std::string& line) {
    JobInfo job;
    std::istringstream iss(line);
    iss >> job.duration;
    int s;
    while (iss >> s) {
        job.successors.push_back(s);
    }
    return job;
}
// ============================================================
// 主程序：关键路径法（CPM）
// ============================================================
int main() {
    // ---- 读取任务数量 ----
    int N;
    std::cin >> N;
    std::vector<JobInfo> jobs(N);
    // ---- 读取每个任务的信息 ----
    // 格式：每行 "持续时间 [后继任务编号...]"
    std::string dummy;
    std::getline(std::cin, dummy); // 消耗掉 N 后面的换行符
    for (int i = 0; i < N; i++) {
        std::string line;
        std::getline(std::cin, line);
        jobs[i] = parseJobLine(line);
    }
    // ---- 建图 ----
    // 图共有 2*N + 2 个顶点：
    //   顶点 i       = 任务 i 的开始节点（0 <= i < N）
    //   顶点 i + N   = 任务 i 的结束节点（0 <= i < N）
    //   顶点 2*N     = 超级源点 s
    //   顶点 2*N + 1 = 超级汇点 t
    int s = 2 * N;     // 超级源点
    int t = 2 * N + 1; // 超级汇点
    EdgeWeightedDigraph G(2 * N + 2);
    for (int i = 0; i < N; i++) {
        double duration = jobs[i].duration;
        // 边1：任务 i 的开始 → 任务 i 的结束，权重 = 持续时间
        G.addEdge(DirectedEdge(i, i + N, duration));
        // 边2：超级源点 → 任务 i 的开始，权重 = 0
        G.addEdge(DirectedEdge(s, i, 0.0));
        // 边3：任务 i 的结束 → 超级汇点，权重 = 0
        G.addEdge(DirectedEdge(i + N, t, 0.0));
        // 边4（前置约束）：对于每个后继任务 j
        //   任务 i 的结束 → 任务 j 的开始，权重 = 0（表示 j 必须在 i 完成后开始）
        for (int j : jobs[i].successors) {
            G.addEdge(DirectedEdge(i + N, j, 0.0));
        }
    }
    // ---- 求 DAG 最长路径 ----
    AcyclicLP lp(G, s);
    // ---- 输出结果 ----
    std::cout << "各任务最早开始时间：" << std::endl;
    for (int i = 0; i < N; i++) {
        std::printf("  任务 %2d: %6.1f\n", i, lp.distTo[i]);
    }
    std::printf("最短完工时间: %.1f\n", lp.distTo[t]);
    // ---- 回溯关键路径（从 t 反向追溯） ----
    std::cout << "\n关键路径（从终点反向追溯）:" << std::endl;
    std::vector<int> path;
    int cur = t;
    while (cur != s && cur != -1) {
        path.push_back(cur);
        cur = lp.edgeTo[cur];
    }
    path.push_back(s);
    // 反转为正向
    for (int i = (int)path.size() - 1; i >= 0; i--) {
        int v = path[i];
        if (v == s) std::cout << "  [源点s]";
        else if (v == t) std::cout << " -> [汇点t]";
        else if (v < N) std::cout << " -> 任务" << v << "开始";
        else std::cout << " -> 任务" << (v - N) << "结束";
    }
    std::cout << std::endl;
    return 0;
}

输入格式说明

10
41.0  1 7 9
51.0  2
50.0
36.0
38.0
45.0
21.0  3 8
32.0  3 8
32.0  2
29.0  4 6

预期输出

各任务最早开始时间：
  任务  0:    0.0
  任务  1:   41.0
  任务  2:  123.0
  任务  3:   91.0
  任务  4:   70.0
  任务  5:    0.0
  任务  6:   70.0
  任务  7:   41.0
  任务  8:   91.0
  任务  9:   41.0
最短完工时间: 173.0
关键路径（从终点反向追溯）:
  [源点s] -> 任务0开始 -> 任务0结束 -> 任务9开始 -> 任务9结束 -> 任务6开始 -> 任务6结束 -> 任务8开始 -> 任务8结束 -> 任务2开始 -> 任务2结束 -> [汇点t]

八、时间复杂度分析

命题 U：关键路径法在线性时间内解决并行任务调度问题。

步骤	时间
建图	$O (N + M)$ （ $M$ 为约束数量）
拓扑排序（DFS）	$O (V + E) = O (N + M)$
最长路径（松弛）	$O (V + E) = O (N + M)$
总计	$O (N + M)$ （线性时间）

正确性证明思路：

下界：DAG 中从 $s$ 到任意顶点 $v$ 的任意路径，都对应一组必须串行完成的任务序列。这些任务串行完成的时间就是 $v$ 的完成时间的下界。
因此 $distTo[t]\text{distTo}[t]$ （最长路径长度）是完工时间的下界。
上界：最长路径给出的调度方案是可行的——每个任务的开始时间都在其所有前置任务完成之后（因为前置约束边权为 0 但保证了拓扑顺序）。
因此 $distTo[t]\text{distTo}[t]$ 也是一个可以实际达到的完工时间，即上界。
下界 = 上界 → 最优。
$\text{关键路径长度} = \text{最短可能完工时间}$

九、扩展：带相对截止期限的调度

问题升级

在原有约束基础上，增加一类约束：
“任务 $j$ 必须在任务 $i$ 开始后的 $d$ 个时间单位内开始”
例如：

任务 2 必须在任务 4 开始后的 12 个时间单位内开始（ $d = 12$ ）
即：任务 4 的开始时间 $≥\ge$ 任务 2 的开始时间 $- 12$

如何建模？

这类约束等价于：在调度图中，从任务 $j$ 的开始节点到任务 $i$ 的开始节点加一条权重为 $- d$ 的边：
$\text{start}(i) \le \text{start}(j) + d \quad \Longleftrightarrow \quad \text{start}(i) - \text{start}(j) \le d$
这意味着图中会出现负权边，并且由于截止约束可能形成环（例如 $i$ 约束 $j$ ， $j$ 又约束 $i$ ）。
命题 V：带相对截止期的并行调度，等价于带负权边的有向图中的最短路径问题（可能有环）。
将图中所有权重取反，最长路径变为最短路径。此时需要使用 Bellman-Ford 算法：

若存在负权环，则说明约束互相矛盾，调度不可行。
若无负权环，则 Bellman-Ford 给出最优调度。

负权边示意

             -12（截止约束：2必须在4开始后12单位内开始）
任务2开始  <----------  任务4开始

场景	算法	能处理负权？	能处理环？
无截止约束	AcyclicLP（拓扑+DP）	能（非负即可）	不能（需是DAG）
有截止约束	Bellman-Ford	能	能
Dijkstra	—	不能	—

十、完整流程总结（ASCII 流程图）

输入：N个任务（持续时间 + 前置约束）
         |
         v
    构造 DAG
    ┌─────────────────────────────────┐
    │  2N+2 个顶点                    │
    │  • 超级源点 s → 每个任务开始(权0) │
    │  • 每个任务：开始→结束(权=时长)  │
    │  • 前置约束：结束→后继开始(权0)  │
    │  • 每个任务结束 → 超级汇点 t(权0)│
    └─────────────────────────────────┘
         |
         v
    拓扑排序（DFS 逆后序）
         |
         v
    按拓扑序松弛所有边
    distTo[v] = max(distTo[v], distTo[u] + w(u,v))
         |
         v
    输出：distTo[i] = 任务i最早开始时间
          distTo[t] = 最短完工时间（关键路径长度）

十一、Java vs C++ 对照表

Java 写法	C++ 对应写法
`StdIn.readInt()`	`std::cin >> N`
`StdIn.readLine()`	`std::getline(std::cin, line)`
`String.split("\\s+")`	`std::istringstream` 逐词读取
`StdOut.printf(...)`	`std::printf(...)`
`EdgeWeightedDigraph` 类	自定义 `EdgeWeightedDigraph` 结构体
`AcyclicLP` 类	自定义 `AcyclicLP` 类
`double` 负无穷	`std::numeric_limits<double>::infinity()`

核心思想一句话总结：把调度问题的"最短完工时间"，转化为 DAG 上从超级源点到超级汇点的"最长路径长度"，用拓扑排序 + 动态规划在线性时间内求解。

一般有向图中的最短路径：Bellman-Ford 算法与套汇问题

基于《算法（第4版）》4.4节，改写为 C++ 视角，配详细中文解析与完整可运行代码。

一、引入：负权边带来了什么新问题？

上一节讲到，带权 DAG 的最短路径可以用拓扑排序解决；Dijkstra 算法适用于正权边的有向图。
但现实中，负权边大量存在（例如带截止期限的任务调度）。
负权边对最短路径的直觉影响：

正权图中，路径越短（边越少）越好，我们找"捷径"。
负权图中，我们反而想要"绕弯路"——多走几条负权边，总权重反而更小。

二、三种错误的"草率想法"

草率想法一：把所有边权加上一个正数让权重非负

做法：找到最小（最负）的边权 $w_{\min}$ ，把所有边权加上 $w_{\min}|$ 。
为什么不行？
路径经过的边越多，被"惩罚"越多。原来最短的路径（边多但总权小）在变换后可能变得比原来长的路径还差。变换前后的最短路径没有对应关系。

草率想法二：改造 Dijkstra 算法

Dijkstra 的核心假设：每次从优先队列取出的顶点，其最短距离已经确定，不会再被更新。这依赖于"给路径加一条边，路径只会更长"。
一旦有负权边，加边反而会让路径变短，这个假设就被打破了，Dijkstra 算法会给出错误答案。

草率想法三：找最短简单路径

即使有负权环，两个顶点之间的最短简单路径（不重复顶点）总是存在的。
为什么不行？ 目前已知求最短简单路径的最好算法在最坏情况下是指数时间的（详见第6章，NP难问题）。对于实际应用来说太慢了。

三、负权环：让最短路径变成无意义的概念

什么是负权环？

$\text{有向环 } v_0 \to v_1 \to \cdots \to v_k \to v_0 \text{ 的总权重} < 0$
例子：边 $\to 7$ （权 0.37）， $\to 5$ （权 0.28）， $\to 4$ （权 -0.66），构成环：
$0.37 + 0.28 + (- 0.66) = - 0.01$
只要在这个环上多转一圈，路径总权重就减少 0.01。转无限圈就能得到负无穷的路径权重——最短路径不存在。

命题 W（最短路径存在的条件）

从 $s$ 到 $v$ 存在最短路径，当且仅当：

存在从 $s$ 到 $v$ 的至少一条有向路径，且
从 $s$ 到 $v$ 的所有路径上，没有任何顶点处于负权环上。

三类情况总结

顶点分类：
┌─────────────────────────────────────────────┐
│  灰色：从 s 不可达            distTo = +∞   │
│  白色：可达但路径经过负权环   distTo = +∞   │
│  黑色：可达且无负权环污染     有确定最短路径 │
└─────────────────────────────────────────────┘

四、Bellman-Ford 算法

核心思想

不依赖边的顺序，对所有边进行 $V$ 轮松弛。
命题 X（Bellman-Ford 正确性）：
初始化 $distTo[s]=0\text{distTo}[s] = 0$ ，其余为 $+∞+\infty$ 。对所有边进行松弛，重复 $V$ 次。若图中无从 $s$ 可达的负权环，则结束后 $distTo[v]\text{distTo}[v]$ 即为从 $s$ 到 $v$ 的最短路径长度。
为什么 $V$ 轮足够？
任何不经过负权环的最短路径，最多包含 $V - 1$ 条边。归纳可证：第 $i$ 轮结束后，所有最多经过 $i$ 条边的最短路径都已正确计算。
时间复杂度： $O (V E)$ （ $V$ 轮，每轮松弛 $E$ 条边）
空间复杂度： $O (V)$

五、基于队列的 Bellman-Ford（优化版本）

关键观察

朴素版本每轮都松弛所有 $E$ 条边，但实际上，只有上一轮 $distTo\text{distTo}$ 值发生变化的顶点，其出边才可能在下一轮导致新的更新。

优化策略

用一个 FIFO 队列跟踪"上一轮被更新的顶点"，只对这些顶点的出边进行松弛。

数据结构

变量	类型	作用
`distTo[]`	`double[]`	从源点到各顶点的最短距离
`edgeTo[]`	有向边数组	最短路径树中各顶点的前驱边
`onQ[]`	`bool[]`	顶点是否在队列中（避免重复入队）
`queue`	FIFO队列	待松弛的顶点列表
`cost`	`int`	松弛次数计数器（用于定期检测负权环）

算法执行演示（有负权边的例子）

图的边信息（tinyEWDn.txt）：

边             权重
0->2          0.26
0->4          0.38
4->5          0.35
4->7          0.37
5->4          0.35
5->7          0.28
5->1          0.32
7->3          0.39
7->5          0.28
1->3          0.29
2->7          0.34
3->6          0.52
6->2         -1.20
6->0         -1.40
6->4         -1.25

第1轮（源点0出发）：
  队列: [0]
  松弛 0->2: distTo[2]=0.26, 入队2
  松弛 0->4: distTo[4]=0.38, 入队4
第2轮：
  队列: [2, 4]
  松弛 2->7: distTo[7]=0.60, 入队7
  松弛 4->5: distTo[5]=0.73, 入队5
  松弛 4->7: 0.38+0.37=0.75 > 0.60, 不更新
第3轮：
  队列: [7, 5]
  松弛 7->3: distTo[3]=0.99, 入队3
  松弛 5->1: distTo[1]=1.05, 入队1
  松弛 5->4: 0.73+0.35=1.08 > 0.38, 不更新
第4轮：
  队列: [3, 1]
  松弛 3->6: distTo[6]=1.51, 入队6
第5轮（负权边生效！）：
  队列: [6]
  松弛 6->4: distTo[4]=1.51+(-1.25)=0.26  更新！入队4
  （同理 6->0, 6->2 也可能更新）
第6~8轮：
  4被更新后，4->5->1 都需要重新松弛...
  最终 distTo[1]=0.93（比之前的1.05更短）

最终结果：

distTo[0]=0.00  distTo[1]=0.93  distTo[2]=0.26
distTo[3]=0.99  distTo[4]=0.26  distTo[5]=0.61
distTo[6]=1.51  distTo[7]=0.60

六、负权环检测

检测方法

在 edgeTo[] 数组中，如果存在有向环，该环必然是负权环（因为一个顶点被第二次加入最短路径，意味着第二次的距离更小，说明绕了一圈后路径变短了）。
每隔 $V$ 次松弛，检查一次 edgeTo[] 中是否有环。

如何在 `edgeTo[]` 中找环？

把 edgeTo[] 中所有非空边构成一个新图，对这个子图用 DFS 检测有向环。

七、完整 C++ 实现

#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <limits>
#include <cmath>
#include <string>
#include <sstream>
#include <iomanip>
// ============================================================
// 有向加权边
// ============================================================
struct DirectedEdge {
    int u, v;       // 起点和终点
    double w;       // 边权
    DirectedEdge() : u(-1), v(-1), w(0) {}
    DirectedEdge(int u, int v, double w) : u(u), v(v), w(w) {}
};
// ============================================================
// 有向加权图（邻接表）
// ============================================================
class EdgeWeightedDigraph {
public:
    int V;
    std::vector<std::vector<DirectedEdge>> adj;
    EdgeWeightedDigraph(int v) : V(v), adj(v) {}
    void addEdge(const DirectedEdge& e) {
        adj[e.u].push_back(e);
    }
};
// ============================================================
// 在 edgeTo[] 子图中检测有向环（DFS）
// ============================================================
class CycleFinder {
public:
    std::vector<bool> visited;
    std::vector<bool> onStack;   // 当前 DFS 栈上的顶点（用于检测环）
    std::vector<int> edgeTo;     // 前驱顶点（用于回溯环路径）
    std::vector<DirectedEdge> cycle; // 检测到的环（边序列）
    bool hasCycle;
    CycleFinder(const EdgeWeightedDigraph& G)
        : visited(G.V, false), onStack(G.V, false),
          edgeTo(G.V, -1), hasCycle(false)
    {
        for (int v = 0; v < G.V && !hasCycle; v++) {
            if (!visited[v]) dfs(G, v);
        }
    }
    void dfs(const EdgeWeightedDigraph& G, int v) {
        visited[v] = true;
        onStack[v] = true; // 进入 DFS 栈
        for (const auto& e : G.adj[v]) {
            if (hasCycle) return;
            if (!visited[e.v]) {
                edgeTo[e.v] = v;
                dfs(G, e.v);
            } else if (onStack[e.v]) {
                // 发现环：e.v 在当前栈上，说明有环
                hasCycle = true;
                // 回溯收集环上的边
                cycle.clear();
                // 从 v 回溯到 e.v
                std::stack<int> path;
                int cur = v;
                while (cur != e.v) {
                    path.push(cur);
                    cur = edgeTo[cur];
                }
                path.push(e.v);
                // 收集路径上的边（这里简化：只记录顶点序列）
                // 实际环的边在 edgeTo[] 子图中
                return;
            }
        }
        onStack[v] = false; // 离开 DFS 栈
    }
};
// ============================================================
// 基于队列的 Bellman-Ford 最短路径算法
// ============================================================
class BellmanFordSP {
private:
    int V;
    std::vector<double> distTo;        // distTo[v] = 源点到 v 的最短距离
    std::vector<DirectedEdge> edgeTo;  // edgeTo[v] = 最短路径树中到达 v 的边
    std::vector<bool> onQ;             // onQ[v] = v 是否在队列中
    std::queue<int> q;                 // 待松弛的顶点队列
    int cost;                          // 松弛次数（用于定期检测负权环）
    std::vector<int> negCycle;         // 负权环顶点序列（空表示没有）
    bool hasNegCycle;                  // 是否存在负权环
    // 松弛顶点 v 的所有出边
    void relax(const EdgeWeightedDigraph& G, int v) {
        for (const auto& e : G.adj[v]) {
            int w = e.v;
            // 如果经过 v 到 w 的路径更短，则更新
            if (distTo[w] > distTo[v] + e.w) {
                distTo[w] = distTo[v] + e.w;
                edgeTo[w] = e;
                // 将 w 加入队列（若未在队列中）
                if (!onQ[w]) {
                    q.push(w);
                    onQ[w] = true;
                }
            }
            // 每隔 V 次松弛，检测一次负权环
            if (++cost % V == 0) {
                findNegativeCycle(G);
                if (hasNegCycle) return; // 发现负权环，立即停止
            }
        }
    }
    // 在 edgeTo[] 构成的子图中寻找有向环
    // 若该子图有环，则该环必为负权环
    void findNegativeCycle(const EdgeWeightedDigraph& G) {
        // 构造 edgeTo[] 子图
        EdgeWeightedDigraph spt(V);
        for (int v = 0; v < V; v++) {
            if (edgeTo[v].u != -1) { // 该边存在
                spt.addEdge(edgeTo[v]);
            }
        }
        // 用 DFS 检测子图中的环
        CycleFinder cf(spt);
        if (cf.hasCycle) {
            hasNegCycle = true;
            // 回溯找出负权环上的顶点
            // 找到环的入口点（onStack 中某个被重复访问的点）
            // 简化实现：直接标记 hasNegCycle，环路径通过 edgeTo[] 可追溯
        }
    }
public:
    BellmanFordSP(const EdgeWeightedDigraph& G, int s)
        : V(G.V),
          distTo(G.V, std::numeric_limits<double>::infinity()),
          edgeTo(G.V),        // 默认构造（u=-1表示无效边）
          onQ(G.V, false),
          cost(0),
          hasNegCycle(false)
    {
        distTo[s] = 0.0;
        q.push(s);
        onQ[s] = true;
        // 主循环：队列非空且无负权环则继续
        while (!q.empty() && !hasNegCycle) {
            int v = q.front(); q.pop();
            onQ[v] = false;
            relax(G, v);
        }
    }
    // 查询到顶点 v 的最短距离
    double dist(int v) const {
        return distTo[v];
    }
    // 是否有从源点到 v 的路径
    bool hasPathTo(int v) const {
        return distTo[v] < std::numeric_limits<double>::infinity();
    }
    // 是否存在负权环
    bool hasNegativeCycle() const {
        return hasNegCycle;
    }
    // 打印从源点到 v 的最短路径
    void printPathTo(int v) const {
        if (!hasPathTo(v)) {
            std::cout << "  无路径可达" << std::endl;
            return;
        }
        std::stack<DirectedEdge> path;
        int cur = v;
        while (edgeTo[cur].u != -1) {
            path.push(edgeTo[cur]);
            cur = edgeTo[cur].u;
        }
        while (!path.empty()) {
            auto e = path.top(); path.pop();
            std::cout << "  " << e.u << " -> " << e.v
                      << "  (权重: " << e.w << ")" << std::endl;
        }
    }
};
// ============================================================
// 套汇检测（Arbitrage）
// ============================================================
void solveArbitrage() {
    // 输入格式：
    // 第一行：货币数量 V
    // 接下来 V 行：货币名称 + V 个汇率
    // 示例数据（5种货币）
    int V = 5;
    std::string names[] = {"USD", "EUR", "GBP", "CHF", "CAD"};
    // 汇率矩阵 rate[i][j] = 用货币i换货币j的汇率
    double rate[5][5] = {
        {1,     0.741, 0.657, 1.061, 1.005},
        {1.349, 1,     0.888, 1.433, 1.366},
        {1.521, 1.126, 1,     1.614, 1.538},
        {0.942, 0.698, 0.619, 1,     0.953},
        {0.995, 0.732, 0.650, 1.049, 1    }
    };
    // 建图：边权 = -ln(汇率)
    // 原因：乘积最大化 <=> 对数之和最大化 <=> 负对数之和最小化
    // 套汇机会 <=> 负权环（绕一圈后对数之和为负，即乘积大于1）
    EdgeWeightedDigraph G(V);
    for (int i = 0; i < V; i++) {
        for (int j = 0; j < V; j++) {
            // 边权 = -ln(rate[i][j])
            // 若存在负权环，则该环对应一个套汇机会
            G.addEdge(DirectedEdge(i, j, -std::log(rate[i][j])));
        }
    }
    // 以顶点 0（USD）为源点运行 Bellman-Ford
    BellmanFordSP bf(G, 0);
    std::cout << "=== 套汇检测 ===" << std::endl;
    if (bf.hasNegativeCycle()) {
        std::cout << "发现套汇机会！" << std::endl;
        std::cout << "（注：本简化版本标记了存在，完整环路追踪见下方手动演示）" << std::endl;
    } else {
        std::cout << "无套汇机会" << std::endl;
    }
    // 手动演示已知的套汇路径：USD -> EUR -> CAD -> USD
    std::cout << "\n演示套汇路径 USD -> EUR -> CAD -> USD：" << std::endl;
    double stake = 1000.0;
    std::cout << std::fixed << std::setprecision(5);
    std::cout << "  " << stake << " USD";
    stake *= rate[0][1]; // USD -> EUR
    std::cout << " -> " << stake << " EUR" << std::endl;
    std::cout << "  " << stake << " EUR";
    stake *= rate[1][4]; // EUR -> CAD
    std::cout << " -> " << stake << " CAD" << std::endl;
    std::cout << "  " << stake << " CAD";
    stake *= rate[4][0]; // CAD -> USD
    std::cout << " -> " << stake << " USD" << std::endl;
    std::cout << "  利润: " << (stake - 1000.0) << " USD ("
              << ((stake / 1000.0 - 1.0) * 100.0) << "%)" << std::endl;
}
// ============================================================
// 主程序：测试 Bellman-Ford 算法
// ============================================================
int main() {
    std::cout << "=== 测试1：含负权边的最短路径 ===" << std::endl;
    // 构造 tinyEWDn 图（8个顶点，含负权边）
    EdgeWeightedDigraph G(8);
    G.addEdge({4, 5,  0.35});
    G.addEdge({5, 4,  0.35});
    G.addEdge({4, 7,  0.37});
    G.addEdge({5, 7,  0.28});
    G.addEdge({7, 5,  0.28});
    G.addEdge({5, 1,  0.32});
    G.addEdge({0, 4,  0.38});
    G.addEdge({0, 2,  0.26});
    G.addEdge({7, 3,  0.39});
    G.addEdge({1, 3,  0.29});
    G.addEdge({2, 7,  0.34});
    G.addEdge({6, 2, -1.20}); // 负权边
    G.addEdge({3, 6,  0.52});
    G.addEdge({6, 0, -1.40}); // 负权边
    G.addEdge({6, 4, -1.25}); // 负权边
    BellmanFordSP sp(G, 0);
    if (sp.hasNegativeCycle()) {
        std::cout << "检测到负权环，最短路径无意义！" << std::endl;
    } else {
        std::cout << "从源点 0 出发的最短距离：" << std::endl;
        for (int v = 0; v < 8; v++) {
            std::cout << std::fixed << std::setprecision(2);
            std::cout << "  到顶点 " << v << ": ";
            if (sp.hasPathTo(v))
                std::cout << sp.dist(v) << std::endl;
            else
                std::cout << "不可达" << std::endl;
        }
        std::cout << "\n到顶点 1 的最短路径：" << std::endl;
        sp.printPathTo(1);
    }
    std::cout << std::endl;
    // 测试2：含负权环的图
    std::cout << "=== 测试2：含负权环的图 ===" << std::endl;
    EdgeWeightedDigraph G2(8);
    G2.addEdge({4, 5,  0.35});
    G2.addEdge({5, 4, -0.66}); // 负权边，与4->7->5->4构成负权环
    G2.addEdge({4, 7,  0.37});
    G2.addEdge({5, 7,  0.28});
    G2.addEdge({7, 5,  0.28});
    G2.addEdge({5, 1,  0.32});
    G2.addEdge({0, 4,  0.38});
    G2.addEdge({0, 2,  0.26});
    G2.addEdge({7, 3,  0.39});
    G2.addEdge({1, 3,  0.29});
    G2.addEdge({2, 7,  0.34});
    G2.addEdge({6, 2,  0.40});
    G2.addEdge({3, 6,  0.52});
    G2.addEdge({6, 0,  0.58});
    G2.addEdge({6, 4,  0.93});
    BellmanFordSP sp2(G2, 0);
    if (sp2.hasNegativeCycle()) {
        std::cout << "检测到负权环！调度/路径问题不可行。" << std::endl;
    } else {
        std::cout << "无负权环，正常输出最短路径。" << std::endl;
    }
    std::cout << std::endl;
    // 测试3：套汇问题
    solveArbitrage();
    return 0;
}

八、算法流程图

九、套汇问题详解

什么是套汇？

在货币兑换市场中，如果存在一组货币 $c1→c2→⋯→ck→c1c_1 \to c_2 \to \cdots \to c_k \to c_1$ ，使得：
$r_{c_1 c_2} \times r_{c_2 c_3} \times \cdots \times r_{c_k c_1} > 1$
则可以用 $x$ 单位的 $c_1$ ，经过这些兑换后，得到超过 $x$ 单位的 $c_1$ ，从而无风险获利。

如何转化为最短路径问题？

命题 Z：套汇问题等价于带权有向图中的负权环检测问题。
关键变换：对每条汇率边取负自然对数作为新的边权：
$\to t) = -\ln(r_{st})$
原因：

原问题：乘积 $r1×r2×⋯×rk>1r_1 \times r_2 \times \cdots \times r_k > 1$
两边取对数： $ln⁡r1+ln⁡r2+⋯+ln⁡rk>0\ln r_1 + \ln r_2 + \cdots + \ln r_k > 0$
取反： $(−ln⁡r1)+(−ln⁡r2)+⋯+(−ln⁡rk)<0(-\ln r_1) + (-\ln r_2) + \cdots + (-\ln r_k) < 0$
这正好对应新图中的负权环！

数值示例

汇率表（部分）：

从\到	USD	EUR	CAD
USD	1	0.741	1.005
EUR	1.349	1	1.366
CAD	0.995	0.732	1

套汇路径：USD $→\to$ EUR $→\to$ CAD $→\to$ USD
$0.741 \times 1.366 \times 0.995 = 1.00714\cdots > 1$
变换后的边权（取负对数）：
$-\ln(0.741) - \ln(1.366) - \ln(0.995) = 0.2998 - 0.3119 + 0.0050 = -0.0071 < 0$
负权环得证！
实际利润（以1000 USD为本）：

1000.00 USD
  × 0.741  = 741.00 EUR
  × 1.366  = 1012.206 CAD
  × 0.995  = 1007.145 USD
利润 = 7.145 USD（0.714%）
按每分钟交易100万USD计算 ≈ 每分钟盈利 7145 USD

套汇的图示

环的总边权： $0.300 + (- 0.312) + 0.005 = - 0.007 < 0$ ，即负权环，对应套汇机会。

十、三种最短路径算法对比

算法	限制条件	典型时间	最坏时间	额外空间	适用场景
Dijkstra（堆优化）	边权必须非负	$\log V)$	$\log V)$	$O (V)$	正权图，最优选择
拓扑排序法	图必须是 DAG	$O (E + V)$	$O (E + V)$	$O (V)$	无环图，线性时间最优
Bellman-Ford（队列版）	无负权环即可	$O (E + V)$	$O (V E)$	$O (V)$	通用，可检测负权环

选择策略：

图有负权边？
  ├─ 否 → Dijkstra（最快）
  └─ 是
       图有环？
         ├─ 否 → 拓扑排序法（线性时间）
         └─ 是 → Bellman-Ford（兼顾正确性与负权环检测）

十一、关键性质总结

命题 Y（队列版 Bellman-Ford 的保证）：
若图中无从源点 $s$ 可达的负权环，算法在经过不超过 $V - 1$ 轮松弛后终止，时间 $O (V E)$ ，空间 $O (V)$ 。
若存在从 $s$ 可达的负权环，队列永远不会变空，第 $V$ 轮后 edgeTo[] 子图中必然含有环，该环即为负权环。
为什么 edgeTo[] 中的环一定是负权环？
若顶点 $w$ 在第 $V$ 轮后被第二次加入路径，说明第二次到达 $w$ 的路径比第一次更短（否则不会更新），绕了一圈路径反而变短——这正是负权环的定义。

核心思想一句话总结：Bellman-Ford 用"反复松弛所有可能有效的边（队列驱动）+ 定期检测 edgeTo[] 子图中的环"，在 $O (V E)$ 时间内解决含负权边的最短路径问题，并顺带检测负权环（套汇机会）。

天工造物局

北京人形旗下天工造物具身智能开源社区，聚焦具身天工与慧思开物两大平台

更多推荐

deck.gl TripsLayer 出租车轨迹动画示例实战：从示例运行到着色器原理

TripsLayer 是 deck.gl 中用于渲染**随时间流动的轨迹动画**（如出租车行程、物流路径、迁徙路线）的核心图层。本文以仓库中的最小独立示例 [examples/website/trips](https://link.gitcode.com/i/1442af8f442f4cff39ff546e050fceb5) 为骨架，带你完成从安装依赖、启动应用、理解曼哈顿出租车数据格式，到深入

天工造物局

Foundry Anvil 中 eth_simulateV1 的 Blob 交易与 Blob Gas 字段规范化：原理、实现与测试验证

本篇技术指南以 [anvil-simulate-blob-transactions.md](https://link.gitcode.com/i/3d2ebe227262de169335eb290af80da8) 这条 changelog 条目为起点，深入剖析 Foundry Anvil 对 `eth_simulateV1` RPC 返回结果中 blob（EIP-4844）交易与 blob gas

天工造物局

LMCache CLI 实战：用 `lmcache kvcache clear` 管理运行中服务的 KV Cache 状态

本文是一份针对 LMCache 官方 CLI 命令 `lmcache kvcache` 的完整技术指南。该命令用于在**运行中的 LMCache 服务（MP HTTP server）**上管理 KV cache 状态，当前提供 `clear` 子命令，用于清空 L1（CPU 内存）层中缓存的全部 KV 数据。读完本文，你将掌握该命令的完整参数体系、退出码语义、终端/JSON/静默三种输出模式，并能

天工造物局

所有评论(0)

查看更多评论

虾球xz

@TM1695648164

已为社区贡献6条内容

Algorithms_4th学习:有向无环图（DAG）上的最短路径与最长路径

虾球xz

一、为什么 DAG 能做得更好？

二、核心思想：拓扑顺序松弛

三、命题 S：DAG 最短路径线性时间

四、拓扑排序回顾（DFS 后序逆置）

五、算法执行追踪（tinyEWDAG，源点 5）

六、最长路径：取反转化

七、C++ 完整实现

八、算法对比总览

九、预期输出

十、关键点总结

并行任务调度与关键路径法（CPM）

一、问题描述

什么是并行任务调度？

问题的本质

二、样例问题

三、关键路径是什么？

四、建图方法：把调度问题变成最长路径问题

图的构造规则

为什么这样建图有效？

图示（本例 DAG）

五、Mermaid 图示：DAG 结构

六、算法流程

七、完整 C++ 实现

输入格式说明

预期输出

八、时间复杂度分析

命题 U：关键路径法在线性时间内解决并行任务调度问题。

九、扩展：带相对截止期限的调度

问题升级

如何建模？

负权边示意

十、完整流程总结（ASCII 流程图）

十一、Java vs C++ 对照表

一般有向图中的最短路径：Bellman-Ford 算法与套汇问题

一、引入：负权边带来了什么新问题？

二、三种错误的"草率想法"

草率想法一：把所有边权加上一个正数让权重非负

草率想法二：改造 Dijkstra 算法

草率想法三：找最短简单路径

三、负权环：让最短路径变成无意义的概念

什么是负权环？

命题 W（最短路径存在的条件）

三类情况总结

四、Bellman-Ford 算法

核心思想

五、基于队列的 Bellman-Ford（优化版本）

关键观察

优化策略

数据结构

算法执行演示（有负权边的例子）

六、负权环检测

检测方法

如何在 edgeTo[] 中找环？

七、完整 C++ 实现

八、算法流程图

九、套汇问题详解

什么是套汇？

如何转化为最短路径问题？

数值示例

汇率表（部分）：

套汇的图示

十、三种最短路径算法对比

十一、关键性质总结

所有评论(0)

温馨提示：您尚未绑定手机号

虾球xz

如何在 `edgeTo[]` 中找环？