Maximum path length between two vertices in a DAG

H

Helen Grey

Guest
Given a Directed Acyclic Graph, G and two vertices u and v, I need to find the longest u-v path in G. setCosts() function recursively updates the max path length from u to all its neighbors. Once we update the path_cost[] value for some vertex the path_costs[] values of all its children are also updated. For the example below, the code returns wrong values for some of the vertices. Please advise advise what's wrong with the algorithm.

import java.util.Iterator;
import java.util.LinkedList;
public class DAG2 {
int vertex;
LinkedList<Integer> list[];
int path_costs[] = new int[8];



public DAG2(int vertex) {



this.vertex = vertex;
list = new LinkedList[vertex];
for (int i = 0; i <vertex ; i++) {
list = new LinkedList<>();
}

for(int i = 0; i < vertex; i++)
path_costs = 0;
}

public void addEdge(int source, int destination){

//add edge
list[source].addFirst(destination);

}


public void setCost(int v) {

for(int i = 0; i < list[v].size(); i++) {
path_costs[list[v].get(i)] = Math.max(path_costs[v] + 1, path_costs[list[v].get(i)]);
setCost(list[v].get(i));
}
}




public static void main(String args[])
{
DAG2 g = new DAG2(8);

g.addEdge(1, 2);
g.addEdge(1, 3);
g.addEdge(2, 4);
g.addEdge(2, 5);
g.addEdge(3, 6);
g.addEdge(4, 7);
g.addEdge(5, 7);
g.addEdge(6, 5);
g.addEdge(6, 7);
//new
g.addEdge(2, 3);
g.addEdge(3, 5);
g.addEdge(5, 4);

// int a = g.DFS(1, 4);

g.setCost(1);

for(int i = 0; i < g.vertex; i++)
System.out.print(g.path_costs + " ");
}


}

Continue reading...
 
Top