无权无向图中的最长路径

Question

无权无向图中的最长路径

javadata-structuresgraph

4

无向无权图

以该图为参考，假设我想找出从0到5的最长路径。

那么这条路径是：0->1->3->2->4->6->5

有没有好的算法可以解决这个问题？我已经搜索过了，但没有找到我能够理解的算法。我找到了很多关于最短路径（0->1->2->4->6->5）的算法，并且已经成功地实现了它们。也许是我自己的问题，但我希望不是这样 :)

任何帮助都将受到欢迎。

- loveMeansNothing

1

也许可以使用“反向”启发式函数的A*算法？肯定与最长路径问题有关，但似乎涉及的是任意两个节点之间的最长路径。 - tobias_k

@tobias_k 这正是我想要的。任意两个节点之间最长的路径。 - loveMeansNothing

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- kraskevich · Accepted Answer

这个问题是 NP-Hard 的（从哈密顿路径到你的问题有一个简单的约化，而哈密顿路径搜索已知是 NP-Hard）。这意味着对于这个问题没有多项式解（除非 P = NP）。

如果需要精确解，可以使用动态规划（状态数为指数级）：状态是“（已访问的顶点的掩码，最后一个顶点）”，值是 true 或 false。转移是添加一个新的顶点，如果最后一个顶点和新顶点之间有一条边，则该顶点不在掩码中。它的时间复杂度为 O(2^n * n^2)，仍然优于 O(n!) 的回溯法。

以下是动态规划解决方案的伪代码：

f = array of (2 ^ n) * n size filled with false values
f(1 << start, start) = true
for mask = 0 ... (1 << n) - 1:
    for last = 0 ... n - 1:
        for new = 0 ... n - 1:
            if there is an edge between last and new and mask & (1 << new) == 0:
                f(mask | (1 << new), new) |= f(mask, last)
res = 0
for mask = 0 ... (1 << n) - 1:
    if f(mask, end):
        res = max(res, countBits(mask))
return res

关于从哈密顿路径问题到这个问题的约简，我再多说一点：

def hamiltonianPathExists():
    found = false
    for i = 0 ... n - 1:
        for j = 0 ... n - 1:
            if i != j:
                path = getLongestPath(i, j) // calls a function that solves this problem
                if length(path) == n:
                    found = true
    return found

这里是一个 Java 实现（我没有进行充分测试，所以可能存在错误）：

/**
 * Finds the longest path between two specified vertices in a specified graph.
 * @param from The start vertex.
 * @param to The end vertex.
 * @param graph The graph represented as an adjacency matrix.
 * @return The length of the longest path between from and to.
 */
public int getLongestPath(int from, int to, boolean[][] graph) {
    int n = graph.length;
    boolean[][] hasPath = new boolean[1 << n][n];
    hasPath[1 << from][from] = true;
    for (int mask = 0; mask < (1 << n); mask++)
        for (int last = 0; last < n; last++)
            for (int curr = 0; curr < n; curr++)
                if (graph[last][curr] && (mask & (1 << curr)) == 0)
                    hasPath[mask | (1 << curr)][curr] |= hasPath[mask][last];
    int result = 0;
    for (int mask = 0; mask < (1 << n); mask++)
        if (hasPath[mask][to])
            result = Math.max(result, Integer.bitCount(mask));
    return result;
}