图中最长的路径

Question

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

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

Answer 2

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

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

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

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

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

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

Answer 3

您始终可以使用 广度优先搜索 (BFS)，并且每当您添加在图的边缘，你可以得到它的成本作为加法逆元（乘以-1）。这样，您就可以使用最长的边找到“最短路径”。因为您正在进行标量变换，所以您不会失去在组内添加的能力（如果您使用乘法逆元，则会失去这种能力）。

Answer 4

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