图中最长的路径 [英] Longest path in graph

问题描述

由于最近2天，我试图找到一些逻辑计算graph.I最长路径知道我可以很容易找到它的DAG和在总体上是多项式时间algorithm.Formally，我想要实现启发式计算最长路径，morever，如果概率P被赋予与边缘是present图中，我们如何解决problem..help ...

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...

推荐答案

计算最长路径不能在多项式时间内，据我所知完成。下面的Java实现的最长路径算法找到一个积极的加权图对于一个给定源的最长路径，但它需要指数时间在最坏的情况下。

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

}

这篇关于图中最长的路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！