Shortest Path DAG

Master DAG shortest path algorithms, path counting, and topological sorting optimization
Overview

Shortest path problems on DAGs (Directed Acyclic Graphs) have special properties that allow linear O(V+E) time complexity through topological sorting. This chapter explores DAG shortest paths, path counting, critical paths, and other advanced algorithms.
Core Content

1. DAG Shortest Path Algorithm

// DAG shortest path implementation
#include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;

class DAGShortestPath {
private:
    int n;
    vector<vector<pair<int, long long>>> adj;
    vector<int> indegree;
    vector<long long> dist;
    vector<int> parent;
    
public:
    DAGShortestPath(int vertices) : n(vertices) {
        adj.resize(n);
        indegree.resize(n);
        dist.resize(n);
        parent.resize(n);
    }
    
    void addEdge(int u, int v, long long weight) {
        adj[u].push_back({v, weight});
        indegree[v]++;
    }
    
    // Topological sort + shortest path
    bool shortestPath(int source) {
        // Initialize distances
        fill(dist.begin(), dist.end(), LLONG_MAX);
        fill(parent.begin(), parent.end(), -1);
        dist[source] = 0;
        
        // Topological sorting
        queue<int> q;
        vector<int> tempIndegree = indegree;
        
        for (int i = 0; i < n; i++) {
            if (tempIndegree[i] == 0) {
                q.push(i);
            }
        }
        
        vector<int> topoOrder;
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            topoOrder.push_back(u);
            
            for (auto [v, weight] : adj[u]) {
                tempIndegree[v]--;
                if (tempIndegree[v] == 0) {
                    q.push(v);
                }
            }
        }
        
        // Check for cycles
        if (topoOrder.size() != n) {
            return false; // Cycle exists
        }
        
        // Relax edges in topological order
        for (int u : topoOrder) {
            if (dist[u] != LLONG_MAX) {
                for (auto [v, weight] : adj[u]) {
                    if (dist[u] + weight < dist[v]) {
                        dist[v] = dist[u] + weight;
                        parent[v] = u;
                    }
                }
            }
        }
        
        return true;
    }
    
    // Get shortest distance to target
    long long getDistance(int target) {
        return dist[target];
    }
    
    // Reconstruct shortest path
    vector<int> getPath(int target) {
        vector<int> path;
        int current = target;
        
        while (current != -1) {
            path.push_back(current);
            current = parent[current];
        }
        
        reverse(path.begin(), path.end());
        return path;
    }
    
    // Print all shortest distances
    void printDistances(int source) {
        cout << "From node " << source << " shortest distances:" << endl;
        for (int i = 0; i < n; i++) {
            if (dist[i] == LLONG_MAX) {
                cout << "Node " << i << ": unreachable" << endl;
            } else {
                cout << "Node " << i << ": " << dist[i] << endl;
            }
        }
    }
};

// DAG path counting
class DAGPathCounting {
private:
    int n;
    vector<vector<int>> adj;
    vector<int> indegree;
    vector<long long> pathCount;
    
public:
    DAGPathCounting(int vertices) : n(vertices) {
        adj.resize(n);
        indegree.resize(n);
        pathCount.resize(n);
    }
    
    void addEdge(int u, int v) {
        adj[u].push_back(v);
        indegree[v]++;
    }
    
    // Count paths from source to all nodes
    bool countPaths(int source) {
        fill(pathCount.begin(), pathCount.end(), 0);
        pathCount[source] = 1;
        
        // Topological sorting
        queue<int> q;
        vector<int> tempIndegree = indegree;
        
        for (int i = 0; i < n; i++) {
            if (tempIndegree[i] == 0) {
                q.push(i);
            }
        }
        
        vector<int> topoOrder;
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            topoOrder.push_back(u);
            
            for (int v : adj[u]) {
                tempIndegree[v]--;
                if (tempIndegree[v] == 0) {
                    q.push(v);
                }
            }
        }
        
        if (topoOrder.size() != n) {
            return false;
        }
        
        // Count paths in topological order
        for (int u : topoOrder) {
            for (int v : adj[u]) {
                pathCount[v] += pathCount[u];
            }
        }
        
        return true;
    }
    
    long long getPathCount(int target) {
        return pathCount[target];
    }
    
    void printPathCounts(int source) {
        cout << "From node " << source << " path counts:" << endl;
        for (int i = 0; i < n; i++) {
            cout << "Node " << i << ": " << pathCount[i] << endl;
        }
    }
};

// Critical Path Method (CPM)
class CriticalPathMethod {
private:
    int n;
    vector<vector<pair<int, int>>> adj, radj; // Forward and reverse adjacency lists
    vector<int> indegree, outdegree;
    vector<int> earliestTime, latestTime;
    
public:
    CriticalPathMethod(int vertices) : n(vertices) {
        adj.resize(n);
        radj.resize(n);
        indegree.resize(n);
        outdegree.resize(n);
        earliestTime.resize(n);
        latestTime.resize(n);
    }
    
    void addEdge(int u, int v, int duration) {
        adj[u].push_back({v, duration});
        radj[v].push_back({u, duration});
        indegree[v]++;
        outdegree[u]++;
    }
    
    // Calculate critical path
    bool findCriticalPath() {
        // Calculate earliest start times
        fill(earliestTime.begin(), earliestTime.end(), 0);
        
        queue<int> q;
        vector<int> tempIndegree = indegree;
        
        for (int i = 0; i < n; i++) {
            if (tempIndegree[i] == 0) {
                q.push(i);
            }
        }
        
        vector<int> topoOrder;
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            topoOrder.push_back(u);
            
            for (auto [v, duration] : adj[u]) {
                earliestTime[v] = max(earliestTime[v], earliestTime[u] + duration);
                tempIndegree[v]--;
                if (tempIndegree[v] == 0) {
                    q.push(v);
                }
            }
        }
        
        if (topoOrder.size() != n) {
            return false;
        }
        
        // Calculate latest start times
        int projectDuration = *max_element(earliestTime.begin(), earliestTime.end());
        fill(latestTime.begin(), latestTime.end(), projectDuration);
        
        vector<int> tempOutdegree = outdegree;
        queue<int> rq;
        
        for (int i = 0; i < n; i++) {
            if (tempOutdegree[i] == 0) {
                rq.push(i);
            }
        }
        
        while (!rq.empty()) {
            int v = rq.front();
            rq.pop();
            
            for (auto [u, duration] : radj[v]) {
                latestTime[u] = min(latestTime[u], latestTime[v] - duration);
                tempOutdegree[u]--;
                if (tempOutdegree[u] == 0) {
                    rq.push(u);
                }
            }
        }
        
        return true;
    }
    
    // Get critical activities
    vector<pair<int, int>> getCriticalActivities() {
        vector<pair<int, int>> critical;
        
        for (int u = 0; u < n; u++) {
            for (auto [v, duration] : adj[u]) {
                // Check if critical activity
                if (earliestTime[u] + duration == latestTime[v] && 
                    earliestTime[u] == latestTime[u]) {
                    critical.push_back({u, v});
                }
            }
        }
        
        return critical;
    }
    
    void printResults() {
        cout << "Node timing information:" << endl;
        for (int i = 0; i < n; i++) {
            cout << "Node " << i << ": Earliest=" << earliestTime[i] 
                 << ", Latest=" << latestTime[i] << endl;
        }
        
        vector<pair<int, int>> critical = getCriticalActivities();
        cout << "Critical activities:" << endl;
        for (auto [u, v] : critical) {
            cout << u << " -> " << v << endl;
        }
    }
};

int main() {
    // Test DAG shortest path
    DAGShortestPath dag(6);
    dag.addEdge(0, 1, 5);
    dag.addEdge(0, 2, 3);
    dag.addEdge(1, 3, 6);
    dag.addEdge(1, 2, 2);
    dag.addEdge(2, 4, 4);
    dag.addEdge(2, 5, 2);
    dag.addEdge(2, 3, 7);
    dag.addEdge(3, 4, -1);
    dag.addEdge(4, 5, -2);
    
    if (dag.shortestPath(0)) {
        dag.printDistances(0);
        
        vector<int> path = dag.getPath(5);
        cout << "Path to node 5: ";
        for (int i = 0; i < path.size(); i++) {
            cout << path[i];
            if (i < path.size() - 1) cout << " -> ";
        }
        cout << endl;
    }
    
    // Test path counting
    DAGPathCounting pc(4);
    pc.addEdge(0, 1);
    pc.addEdge(0, 2);
    pc.addEdge(1, 3);
    pc.addEdge(2, 3);
    
    if (pc.countPaths(0)) {
        pc.printPathCounts(0);
    }
    
    // Test critical path
    CriticalPathMethod cpm(6);
    cpm.addEdge(0, 1, 3);
    cpm.addEdge(0, 2, 2);
    cpm.addEdge(1, 3, 2);
    cpm.addEdge(2, 3, 4);
    cpm.addEdge(2, 4, 3);
    cpm.addEdge(3, 5, 2);
    cpm.addEdge(4, 5, 1);
    
    if (cpm.findCriticalPath()) {
        cpm.printResults();
    }
    
    return 0;
}
Problem-Solving Tips

🎯 DAG Recognition

After confirming the graph is a DAG, linear time algorithms can be used, detect cycles through topological sorting.
⚡ Complexity Advantage

DAG shortest path O(V+E) is better than Dijkstra O(V log V + E), suitable for large sparse graphs.
🔧 Implementation Points

Topological sort first then relax edges, can handle negative weights, pay attention to initialization and boundary conditions.
🧮 Application Scenarios

Project scheduling, dependency analysis, critical paths, path counting, and other practical problem modeling and solving.