views:

153

answers:

3

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

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

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".

+1  A: 

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

Moron
I guessed so, all I wanted was a catchy name of an European scientist.
Martín Fixman
+1  A: 

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.

ima
+3  A: 

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.

Larry
Thank you! That was exacly what I was looking for!
Martín Fixman