Longest Simple Path in a Directed Acyclic Graph

In a Directed Acyclic Graph (DAG), a longest simple path is the path that traverses the maximum number of edges while not repeating any vertex. This concept is important in optimization problems, task scheduling, and more. Unlike undirected graphs, finding the longest simple path in a DAG is easier and can be solved using dynamic programming.

Dynamic Programming Approach for Longest Weighted Simple Path in a DAG

Algorithm

Initialization: Create a 1-D array distance to store the longest distance from source vertex s to each vertex. Initialize distance[s] to 0 and all other vertices to negative infinity.
Topological Sort: Perform a topological sort on the DAG to determine the sequence in which vertices should be processed.
Dynamic Programming Iteration: For each vertex u, consider every outgoing edge (u, v) with weight w(u, v). Update the distance[v] as max(distance[v], distance[u] + w(u, v)).
Answer Retrieval: The distance[t] would give the longest weighted simple path from s to t.

Subproblem Graph

The subproblem graph would look like the original graph but with vertices annotated with the longest path values from the source vertex s.

Algorithm Efficiency

Topological Sort: (O(V + E))
Initialization: (O(V))
Dynamic Programming Iteration: (O(V + E))

Overall time complexity: (O(V + E)) Space complexity: (O(V))

The algorithm is linear with respect to the number of vertices and edges, making it efficient for sparse graphs.

Java Code for Longest Simple Path in a DAG

Here’s a Java implementation:

 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
32
33
34
import java.util.ArrayList;
import java.util.Arrays;

public class LongestPathDAG {
    public static void main(String[] args) {
        ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
        int vertices = 5;
        for (int i = 0; i < vertices; i++) {
            graph.add(new ArrayList<>());
        }
        graph.get(0).add(1);
        graph.get(1).add(2);
        graph.get(2).add(3);
        graph.get(3).add(4);
        int[] longestPath = new int[vertices];
        Arrays.fill(longestPath, -1);
        for (int i = 0; i < vertices; i++) {
            dfs(i, graph, longestPath);
        }
        System.out.println("Longest Path Length: " + Arrays.stream(longestPath).max().getAsInt());
    }

    public static int dfs(int node, ArrayList<ArrayList<Integer>> graph, int[] longestPath) {
        if (longestPath[node] != -1) {
            return longestPath[node];
        }
        int maxPath = 0;
        for (int neighbor : graph.get(node)) {
            maxPath = Math.max(maxPath, 1 + dfs(neighbor, graph, longestPath));
        }
        longestPath[node] = maxPath;
        return maxPath;
    }
}

C++ Code for Longest Simple Path in a DAG

Here’s a C++ code snippet:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int dfs(int node, vector<vector<int>>& graph, vector<int>& longestPath) {
    if (longestPath[node] != -1) return longestPath[node];
    int maxPath = 0;
    for (int neighbor : graph[node]) {
        maxPath = max(maxPath, 1 + dfs(neighbor, graph, longestPath));
    }
    longestPath[node] = maxPath;
    return maxPath;
}

int main() {
    vector<vector<int>> graph = {{1}, {2}, {3}, {4}, {}};
    vector<int> longestPath(5, -1);
    for (int i = 0; i < 5; ++i) {
        dfs(i, graph, longestPath);
    }
    cout << "Longest Path Length: " << *max_element(longestPath.begin(), longestPath.end()) << endl;
}

Python Code for Longest Simple Path in a DAG

Here’s how you’d write it in Python:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
def dfs(node, graph, longest_path):
    if longest_path[node] != -1:
        return longest_path[node]
    max_path = 0
    for neighbor in graph[node]:
        max_path = max(max_path, 1 + dfs(neighbor, graph, longest_path))
    longest_path[node] = max_path
    return max_path

if __name__ == "__main__":
    graph = {0: [1], 1: [2], 2: [3], 3: [4], 4: []}
    longest_path = [-1] * 5
    for i in range(5):
        dfs(i, graph, longest_path)
    print("Longest Path Length:", max(longest_path))

In these implementations, we use Depth First Search (DFS) to navigate through the graph. We maintain an array called longestPath to store the longest path for each vertex. The DFS function is used to update this array.