DAG 最长路径问题

快速概览

DAG 最长路径问题是曼哈顿游客问题的推广形式，用于在任意有向无环图中寻找权重最大的路径，广泛应用于基因预测、序列组装和进化分析。

• 曼哈顿游客问题是 DAG 最长路径的特例
• 拓扑排序确保正确的 DP 计算顺序
• 时间复杂度 O(|V| + |E|)
• 应用于外显子链、序列比对等问题

前置知识

• 曼哈顿游客问题
• 动态规划
• 图算法基础

所属板块 基础与数学

对象层、坐标系统、coverage 与概率图模型的共同语言。

阅读目标 帮助建立阅读上下文

先判断这页与你当前问题的关系，再决定是否深入展开。

建议前置 先建立相关基础对象与方法直觉

建议先建立相关基础对象与方法直觉，再进入本页。

是什么

DAG 最长路径问题是曼哈顿游客问题（Manhattan Tourist Problem）的推广形式。它不再局限于规则的网格结构，而是适用于任意的有向无环图（Directed Acyclic Graph, DAG）。

问题定义

输入：

• 有向无环图 $G = (V, E)$
• 边权重函数 $w: E \rightarrow \mathbb{R}$
• 源点（source）和汇点（sink）

输出：从源点到汇点的权重最大的路径。

与曼哈顿游客问题的关系

维度	曼哈顿游客	DAG 最长路径
图结构	规则的 $n imes m$ 网格	任意的有向无环图
边方向	只能向南或向东	任意（只要不形成环）
拓扑排序	隐含的（行列顺序）	显式计算或利用 DAG 特性
应用	教学示例、基础 DP	复杂的生物信息学问题

关系：曼哈顿游客问题是 DAG 最长路径问题的特例——网格结构天然构成一个 DAG。

要解决什么生物信息学问题

1. Exon Chaining 问题

在基因预测中，我们需要从候选外显子集合中选择最优的非重叠链。

建模为 DAG：

• 顶点：候选外显子的起始和结束位置
• 边：
  • 外显子边：从起始到结束，权重 = 外显子得分
  • 连接边：从位置 $i$ 到 $i+1$，权重 = 0
• 最长路径 = 最优外显子链

2. 序列比对（Edit Graph）

两个序列的全局比对可以表示为 DAG 中的最长路径：

• 顶点：$(i, j)$ 表示序列 $v$ 的前 $i$ 个字符和序列 $w$ 的前 $j$ 个字符
• 边：
  • 水平边：$(i, j-1) \rightarrow (i, j)$，权重 = 插入罚分
  • 垂直边：$(i-1, j) \rightarrow (i, j)$，权重 = 删除罚分
  • 对角边：$(i-1, j-1) \rightarrow (i, j)$，权重 = 匹配得分或错配罚分

最长路径 = 最优比对。

3. 剪接比对（Spliced Alignment）

结合外显子选择和序列比对：

• 图结构更复杂
• 需要在候选外显子之间进行比对
• 是 DAG 最长路径的高级应用

4. RNA 二级结构预测

某些 RNA 二级结构问题可以建模为 DAG 中的最大权重独立集，与最长路径问题相关。

算法原理

动态规划核心思想

与曼哈顿游客问题相同，DAG 最长路径利用最优子结构性质：

如果 $s \leadsto v \leadsto t$ 是最长路径，那么 $s \leadsto v$ 是到 $v$ 的最长路径。

递推关系

对于每个顶点 $v$，计算从源点到 $v$ 的最长路径长度 $s[v]$：

$s[v] = \max_{(u,v) \in E} \{s[u] + w(u,v)\}$

解释：

• 考虑所有指向 $v$ 的入边 $(u, v)$
• 选择使”到 $u$ 的最长路径 + 边权重”最大的那个
• 这就是到 $v$ 的最长路径

计算顺序：拓扑排序

DAG 的关键性质：存在拓扑排序（顶点线性排序，使得所有边都从左指向右）。

为什么需要拓扑排序：

• 确保计算 $s[v]$ 时，所有 $s[u]$（$u$ 是 $v$ 的前驱）已经计算完毕
• 在曼哈顿游客问题中，自然顺序（逐行逐列）就是一种拓扑排序

拓扑排序算法：

TOPOLOGICAL_SORT(G):
    in_degree = 计算所有顶点的入度
    queue = 所有入度为 0 的顶点
    order = 空列表

    while queue 非空:
        v = queue.dequeue()
        order.append(v)

        for each (v, u) in E:  // v 的所有出边
            in_degree[u] -= 1
            if in_degree[u] == 0:
                queue.enqueue(u)

    return order

完整算法

DAG_LONGEST_PATH(G, w, source, sink):
    // 步骤 1：拓扑排序
    topo_order = TOPOLOGICAL_SORT(G)

    // 步骤 2：初始化
    for each v in V:
        s[v] = -∞
        predecessor[v] = null

    s[source] = 0

    // 步骤 3：按拓扑顺序进行动态规划
    for v in topo_order:
        if s[v] > -∞:  // 可达的顶点
            for each (v, u) in E:  // v 的所有出边
                if s[v] + w(v,u) > s[u]:
                    s[u] = s[v] + w(v,u)
                    predecessor[u] = v

    // 步骤 4：回溯重构路径
    path = []
    v = sink
    while v != null:
        path.prepend(v)
        v = predecessor[v]

    return s[sink], path

复杂度分析

操作	复杂度	说明
拓扑排序	$O(	V
DP 填表	$O(	V
总时间	$O(	V
空间	$O(	V

实例说明

简化示例

图结构：

源点 → A → C → 汇点
  ↘   ↗  ↗
    B → D

边权重：

源点→A: 3, 源点→B: 1
A→C: 4, B→C: 2
B→D: 5, C→汇点: 2
D→汇点: 3, C→D: -1

执行过程：

1. 拓扑排序：源点, A, B, C, D, 汇点

2. 动态规划：

   s[源点] = 0
   
   s[A] = s[源点] + 3 = 3
   
   s[B] = max(s[源点] + 1) = 1
   
   s[C] = max(s[A] + 4, s[B] + 2) = max(7, 3) = 7
   
   s[D] = max(s[B] + 5, s[C] + (-1)) = max(6, 6) = 6
   
   s[汇点] = max(s[C] + 2, s[D] + 3) = max(9, 9) = 9

3. 最长路径（两条）：

   • 源点 → A → C → 汇点（权重 3+4+2=9）
   • 源点 → B → D → 汇点（权重 1+5+3=9）

序列比对的编辑图

将 LCS 问题表示为 DAG：

v = ABC, w = ACB

编辑图（部分）：
    ε   A   C   B
ε   0   0   0   0
A   0   1   1   1
B   0   1   1   2
C   0   1   2   2

最长路径：（0,0）→(1,1)→(3,3)  [对角线匹配 A，然后对角线匹配 C？不对...]

实际最长路径对应 LCS "AC" 或 "AB"，长度 2

与其他问题的联系

最短路径问题

DAG 最长路径可以通过边权重取反转化为最短路径问题：

最长路径（G, w） = 最短路径（G, -w）

注意：这只适用于 DAG，一般图的最长路径问题是 NP-hard。

关键路径方法（CPM）

项目管理中的关键路径分析就是 DAG 最长路径的应用：

• 顶点：任务
• 边：任务依赖关系
• 权重：任务持续时间
• 最长路径 = 项目最短完成时间

实际应用：基因预测中的 Exon Chaining

基因组序列: 0 --- 1 --- 2 --- 3 --- 4 --- 5 --- 6 --- 7 --- 8

候选外显子:
  E1: [1,3] 权重=5
  E2: [2,5] 权重=8
  E3: [4,6] 权重=6
  E4: [6,8] 权重=7

DAG 构建:
  顶点: 0, 1, 2, 3, 4, 5, 6, 7, 8

  区间边:
    (1,3) 权重=5  [E1]
    (2,5) 权重=8  [E2]
    (4,6) 权重=6  [E3]
    (6,8) 权重=7  [E4]

  连接边（权重=0）:
    (0,1), (0,2), (3,4), (3,6), (5,6), (5,8), (6,8), ...

最长路径: 0 → 2 → 5 → 6 → 8
          [E2]    [E4]
          权重 = 8 + 7 = 15

注意: E1和E2重叠，E2和E3重叠，不能同时选

局限性与注意事项

只适用于 DAG

重要：该算法只适用于有向无环图。

如果图中有环：

• 最长路径可能无限（如果环的权重为正）
• 需要更复杂的算法（如 Bellman-Ford 检测负环）

负权重边

DAG 最长路径算法可以处理负权重边：

• 由于拓扑排序的存在，即使边权重为负，DP 依然正确
• 但在某些应用中，负权重可能需要特殊解释

多个源点和汇点

如果图有多个源点或汇点：

• 方法 1：添加超级源点/汇点，连接到所有实际的源点/汇点
• 方法 2：对每个源点分别运行算法，取最大值

常见误区

• DAG 最长路径算法可以用于一般图：
• 不能。一般图（含环）的最长路径问题是 NP-hard 的。DAG 最长路径算法的核心依赖——拓扑排序——在有环图上无法执行。如果图中有正权环，"最长路径"的概念本身就不存在（可以无限绕环增加权重）。
• 拓扑排序结果唯一：
• 同一 DAG 可以有多种合法的拓扑排序。不同的拓扑排序不影响最终的最长路径权重值（因为 DP 递推保证了正确性），但会影响计算的中间过程和回溯路径的构造顺序。
• 最长路径权重之和最大等价于经过的顶点最多：
• 这是两个完全不同的优化目标。例如在 Exon Chaining 中，我们希望总权重最大（选高分外显子），而不是选尽可能多的外显子。一个包含很多低分外显子的链可能总权重远低于少数几个高分外显子的链。

曼哈顿游客问题

DAG 最长路径的特例

延伸阅读

动态规划基础

算法基础

延伸阅读

Exon Chaining

生物信息学应用

延伸阅读

拓扑排序

图算法基础

延伸阅读

总结

• DAG 最长路径是曼哈顿游客问题的推广，适用于任意有向无环图
• 拓扑排序提供了正确的动态规划计算顺序
• 时间复杂度 O(|V| + |E|)，是线性时间算法
• 在生物信息学中广泛应用于基因预测、序列比对等问题
• 理解 DAG 最长路径有助于掌握更复杂的动态规划应用