How to find the longest simple path in a graph?

Question

I know that for an undirected graph this problem is NP-complete, so we need to do Brute Force to check all possible paths. How can we do this? Please suggest pseudo code and tell me the complexity of this algorithm.

If there are optimizations, then that would be great!

Answer 1

A naive approach can go through all possible vertex permutations.

For each permutation {v1, ..., vN} you can check if you can get from v1 to v2 , then from v2 to v3 , etc. If possible, add the appropriate edge length to the current path length. If not, continue to the next permutation.

The longest of these paths is your answer.

---

Or you could do almost the same thing with recursion.

 path = 0 bestPath = 0 used = new bool[N] // initialize with falses for(u = 0; u < N; u++) Path(u); // build paths starting from u print bestPath 

Where

 Path(u) used[u] = true foreach v in neighborhood(u) if(!used[v]) path += distance(u, v) bestPath = max(bestPath, path) Path(v) path -= distance(u, v) used[u] = false 

The complexity of time is terrible O(N * N^N) .

Answer 2

If your schedule is a special case in which it is directed and acyclic , you can use a dynamic programming approach such as described. You basically sort your graph topologically, and then in topological order, for each node V, you check all your neighbors and update their “distance” value if it is greater than the “distance” that is already remembered (initialized with -infinity or something else).

Otherwise, in the general case, the problem is really NP-complete, since it reduces to a Hamiltonian cycle. One thing you could do is nullify all faces and try the Bellman-Ford algorithm. Remember that this is not good for negative loops.