Longest path in graph

Question

Since last 2 days,i'm trying to find some logic for calculating longest path in graph.I know i can find it easily for DAGs and in general it is polynomial time algorithm.Formally,I want to implement heuristic for computing longest path,morever,if probability p is given with which an edge is present in graph,how can we solve the problem..help...

Answer 1

Calculating longest path cannot be done in polynomial time as far as I know. Following java implementation of the longest path algorithm finds the longest path of a positive weighted graph for a given source but it takes exponential time in its worst case.

public class LongestPath {
static int times;
public double initLongestPath(ArrayList<Vertex> V,Vertex source){
    for(Vertex u:V){
        u.setVisited(false);
    }
    return getLongestPath(source);
}
public double getLongestPath(Vertex v){
    ++times;
    System.out.println(times);
    double w,dist,max=0;
    v.setVisited(true);
    for(Edge e:v.getOutGoingEdges()){
        if(!e.getToNode().isVisited()){
            dist=e.getWeight()+getLongestPath(e.getToNode());
            if(dist>max)
                max=dist;
        }
    }

    v.setVisited(false);    
    return max;
}

}