1

从最近两天开始，我试图找到一些计算图中最长路径的逻辑。我知道我可以很容易地为 DAG 找到它，一般来说它是多项式时间算法。形式上，我想实现启发式计算最长路径，此外，如果给出图中边存在的概率 p，我们如何解决这个问题..帮助...

4

4 回答 4

2

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

}

于 2013-05-29T08:43:53.720 回答
1

Dijkstra 不能用于具有负权重的图 -关于 Dijkstra 的 Wiki 文章

Dijkstra 算法，由荷兰计算机科学家 Edsger Dijkstra 于 1956 年构想并于 1959 年发表，是一种图搜索算法，用于解决具有非负边路径成本的图的单源最短路径问题...

所以你不能否定所有边权重并使用 Dijkstra，你可以做的是否定所有边权重并使用 Bellman-Ford 算法 -关于 Bellman-Ford 的维基文章

Bellman-Ford 算法是一种计算从单个源顶点到加权有向图中所有其他顶点的最短路径的算法。1对于相同的问题，它比 Dijkstra 算法慢，但更通用，因为它能够处理一些边权重为负数的图

编辑：最短路径（具有最大负值）是原始图中最长的路径。

注意：如果您的图表中有正循环，您将找不到解决方案，因为最长的路径在这样的图表中不存在。

于 2013-05-02T17:26:19.480 回答
-2

您总是可以只使用广度优先搜索(BFS)，并且每当您向图中添加一条边时，您的成本就是加法逆（乘以 -1）。这样，您就可以通过使用最长的边找到“最短路径”。因为您正在进行标量变换，所以您不会失去在组内添加的能力（如果使用乘法逆运算，您确实会失去这种能力）。

于 2011-11-08T19:39:56.257 回答
-3

反转路径的权重并运行最短路径算法。你得到的最低数字（最负数）是最长的路径。

于 2011-11-08T15:33:24.193 回答