CODEWITHSUNDEEP
algorithmgraphdirected-acyclic-graphs
Frank
Frank

Reputation: 4461

Longest path in a DAG

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?

Upvotes: 16

Views: 35915

Answers (3)

Frank
Frank

Reputation: 4461

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

Upvotes: 3

Sergey Kalinichenko
Sergey Kalinichenko

Reputation: 726479

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.

Upvotes: 11

Pyra
Pyra

Reputation: 179

No DFS needed. Algorithm : takes a DAG G. Each arc holds one variable E

for each node with no predecessor :
    for each of his leaving arcs, E=1.
for each node whose predecessors have all been visited :
    for each of his leaving arcs, E=max(E(entering arcs))+1.

max_path is the highest E within edges when all nodes have been processed.

Upvotes: 3

Related Questions