DAG 上的最短路径问题

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

November 1, 1962基础算法,最短路径问题1分钟阅读

在有向无环图（DAG, Directed Acyclic Graph）上求最短路径，相比通用的图最短路径算法（如 Dijkstra 或 Bellman-Ford），具有显著的高效性与简洁性。

由于 DAG 中不存在环路，我们可以按照节点的拓扑排序（Topological Sort）顺序遍历节点并依次松弛（Relax）其邻接边，从而在 $O(V + E)$ 的线性时间内解决单源最短路径问题。

在任意图的最短路径计算中，环路是导致复杂的根本原因（需要反复松弛或维护优先队列）。而在 DAG 中：

拓扑序列保障依赖关系：如果存在边 $u \to v$ ，则在拓扑序中节点 $u$ 一定排在节点 $v$ 前面。
一次松弛即确定最优：当遍历到节点 $v$ 时，所有能够到达 $v$ 的前驱节点 $u$ 都已经完成最短路径的计算。因此，对 $v$ 的所有出边进行松弛后， $v$ 到其他节点的影响就已完全确定，无需后续重复更新。

初始化距离数组：设定起点 $s$ 的距离 $dist[s] = 0$ ，其余所有节点的距离 $dist[v] = \infty$ 。
拓扑排序：对 DAG 中的所有节点进行拓扑排序，得到节点的线性序列。
按序松弛：按照拓扑排序的顺序依次遍历每个节点 $u$ ：针对节点 $u$ 的每一条权值为 $w(u, v)$ 的出边 $u \to v$ ，若 $dist[u] + w(u, v) < dist[v]$ ，则更新 $dist[v] = dist[u] + w(u, v)$ 。

#include <iostream>
#include <vector>
#include <queue>
#include <climits>

using namespace std;

// 表示有向边：{邻接节点, 边权}
struct Edge {
    int to;
    int weight;
};

// DAG 最短路径算法
void dagShortestPath(int V, int src, const vector<vector<Edge>>& graph) {
    vector<int> inDegree(V, 0);

    // 1. 统计所有节点的入度
    for (int u = 0; u < V; ++u) {
        for (const auto& edge : graph[u]) {
            inDegree[edge.to]++;
        }
    }

    // 2. Kahn 算法求拓扑排序
    queue<int> q;
    for (int i = 0; i < V; ++i) {
        if (inDegree[i] == 0) {
            q.push(i);
        }
    }

    vector<int> topoOrder;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        topoOrder.push_back(u);

        for (const auto& edge : graph[u]) {
            int v = edge.to;
            inDegree[v]--;
            if (inDegree[v] == 0) {
                q.push(v);
            }
        }
    }

    // 3. 初始化距离数组（INT_MAX 表示不可达）
    vector<int> dist(V, INT_MAX);
    dist[src] = 0;

    // 4. 按拓扑序依次松弛出边
    for (int u : topoOrder) {
        // 如果起点无法到达 u，跳过松弛
        if (dist[u] != INT_MAX) {
            for (const auto& edge : graph[u]) {
                int v = edge.to;
                int weight = edge.weight;
                if (dist[u] + weight < dist[v]) {
                    dist[v] = dist[u] + weight;
                }
            }
        }
    }

    // 输出源点到各节点的最短路径距离
    cout << "从源节点 " << src << " 到各个节点的最短路径距离:\n";
    for (int i = 0; i < V; ++i) {
        if (dist[i] == INT_MAX) {
            cout << "节点 " << i << ": 不可达\n";
        } else {
            cout << "节点 " << i << ": " << dist[i] << "\n";
        }
    }
}

int main() {
    int V = 6;
    vector<vector<Edge>> graph(V);

    // 构建 DAG 图 (格式: graph[u].push_back({v, weight}))
    graph[0].push_back({1, 5});
    graph[0].push_back({2, 3});
    graph[1].push_back({2, 2});
    graph[1].push_back({3, 6});
    graph[2].push_back({3, 7});
    graph[2].push_back({4, 4});
    graph[2].push_back({5, 2});
    graph[3].push_back({4, -1}); // 支持负权边
    graph[4].push_back({5, -2});

    int src = 1;
    dagShortestPath(V, src, graph);

    return 0;
}

支持负权边：与 Dijkstra 算法不同，DAG 最短路径算法完美支持负权边（只要图中没有负环即可，而 DAG 连环都没有，自然不存在负环）。
时间复杂度极低：
- 拓扑排序： $O(V + E)$
- 遍历与松弛：每个节点处理一次，每条边松弛一次，时间为 $O(V + E)$
- 总体时间复杂度： $O(V + E)$ ，优于 Dijkstra 的 $O((V + E) \log V)$ 。

核心原理

算法实现

参考代码

核心优势与对比