algorithm - 图中的最长路径

从前两天开始，我一直在尝试寻找一些计算图中最长路径的逻辑。我知道对于dags来说我很容易找到它，而且通常是多项式时间算法。形式上，我想实现计算最长路径的启发式算法，而且，如果概率p是图中存在边的概率p，我们如何解决这个问题..帮助…

最佳答案

据我所知，最长路径的计算不能在多项式时间内完成。在java实现最长路径算法后，可以找到给定源的正加权图的最长路径，但在最坏情况下需要指数时间。

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;
}

}