How is this algorithm, for finding maximum path on a Directed Acyclical Graph, called?
- by Martín Fixman
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".
