未加权无向图中的最长路径

本文介绍了未加权无向图中的最长路径的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

拥有此图表作为参考，假设我想要0到5之间的最长路径。

Having this graph as reference let's say i want the longest path between 0 and 5.

那将是：0-> 1-> 3-> 2-> 4-> 6- > 5

That would be: 0->1->3->2->4->6->5

有没有什么好的算法呢？我搜索过，没有发现任何我能够理解的东西。 我找到了最短路径的很多算法（0-> 1-> 2-> 4-> 6-> 5），我已经成功实现了它们。 也许我是问题，但我想另有想法：）

Is there any good algorithm for this? I've searched and haven't found anything that i was able to understand. I've found plenty algorithms for the shortest path (0->1->2->4->6->5) and i've implemented them successfully. Maybe i'm the problem, but i would like to think otherwise :)

任何帮助将是欢迎

推荐答案

这个问题是NP-Hard（从Hamiltonian路径到你的问题有一个简单的减少，哈密尔顿算法的路径搜索是NP-hard）。这意味着没有多项式解决这个问题（除非P = NP）。

This problem is NP-Hard (there is a simple reduction from a Hamiltonian path to your problem, and a Hamiltonian path search is known to be NP-hard). It means that there is no polynomial solution for this problem (unless P = NP).

如果你需要一个确切的解决方案，你可以使用动态规划状态）：状态为（访问顶点的掩码，last_vertex），该值为true或false。如果 last_vertex 和新顶点之间存在边缘，则转换正在添加不在 mask 中的新顶点。它具有 O（2 ^ n * n ^ 2）时间复杂度，这仍然优于 O（n！）回溯。

If you need an exact solution, you can use dynamic programming (with exponential number of states): the state is (mask of visited vertices, last_vertex), the value is true or false. A transition is adding a new vertex which is not in the mask if there an edge between the last_vertex and the new vertex. It has O(2^n * n^2) time complexity, which is still better than O(n!) backtracking.

这是动态编程解决方案的伪代码：

Here is pseudo code of a dynamic programming solution:

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

还有一点更多关于从哈密尔顿路径减少到这个问题：

And a little bit more about reduction from Hamiltonian path to this problem:

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实现（我没有正确测试，所以它可以包含错误）：

Here is a Java implementation (I did not test properly, so it can contain bugs):

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