Longest path in a DAG

Question

To find the longest path in a DAG, I'm aware of 2 algorithms: algo 1: do a topological sort + use dynamic programming on the result of the sort ~ or ~ algo 2: enumerate all the paths in the DAG using DFS, and record the longest. It seems like enumerating all the paths with DFS has better complexity than algo 1. Is that true?

Answer 1

Your second option is incorrect: DFS does not explore all possible paths, unless your graph is a tree or a forest, and you start from the roots. The second algorithm that I know is negating the weights and finding the shortest path, but it is somewhat slower than the top sort + DP algorithm that you listed as #1.

Answer 2

Enumerate all paths in a DAG using "DFS":

import numpy as np

def enumerate_dag(g):

    def enumerate_r(n, paths, visited, a_path = []):
        a_path += [n]
        visited[n] = 1
        if not g[n]:
            paths += [list(a_path)]
        else:
            for nn in g[n]:
                enumerate_r(nn, paths, visited, list(a_path))

    paths, N = [], len(g)
    visited = np.zeros((N), dtype='int32')

    for root in range(N):
        if visited[root]: continue
        enumerate_r(root, paths, visited, [])

    return paths