algorithm - 图中最长路径

Question

自从过去 2 天以来，我一直在尝试寻找一些计算图中最长路径的逻辑。我知道我可以很容易地为 DAG 找到它，并且通常它是多项式时间算法。形式上，我想实现启发式计算最长的路径，此外，如果给定图中存在边的概率 p，我们如何解决问题..help...

Answer 1

据我所知，计算最长路径不能在多项式时间内完成。以下最长路径算法的 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;
}