Take the 2-minute tour ×

Since some time, I'm using an algorithm that runs in complexity O(V + E) for finding maximum path on a Directed Acyclical Graph from point A to point B, that consists on doing a flood fill to find what nodes are accessible from note A, and how many "parents" (edges that come from other nodes) each node has. Then, I do a BFS but only "activating" a node when I already had used all its "parents".

queue <int> a
int paths[] ; //Number of paths that go to note i
int edge[][] ; //Edges of a
int mpath[] ; //max path from 0 to i (without counting the weight of i)
int weight[] ; //weight of each node

mpath[0] = 0

while not empty(a)
    for i in edge[a]
        paths[i] += 1

while not empty(a)
    for i in children[a]
        mpath[i] = max(mpath[i], mpath[a] + weight[a]) ;

        paths[i] -= 1 ;
        if path[i] = 0
            a.push(i) ;

Is there any special name for this algorithm? I told it to an Informatics professor, he just called it "Maximum Path on a DAG", but it doesn't sound good when you say "I solved the first problem with a Fenwick Tree, the second with Dijkstra, and the third with Maximum Path".

share|improve this question

3 Answers 3

up vote 3 down vote accepted

The is simply just "Longest Path in a DAG" as others mentioned. However, the technique you're using is actually topological sorting with dynamic programming.

share|improve this answer
Thank you! That was exacly what I was looking for! –  Martín Fixman May 17 '10 at 23:43

Probably no - because it's not a common algorithm. When you need to find path in DAG is you just sort it, traverse once and keep longest path.

share|improve this answer

Longest path in a DAG? Make sure you mention DAG. Finding a longest path in general graphs is NP-Complete.

share|improve this answer
I guessed so, all I wanted was a catchy name of an European scientist. –  Martín Fixman May 17 '10 at 5:56

Your Answer


