How to find the longest simple path in a graph?

Question

I know that for non-directed graph this problem is NP-complete hence we should do Brute Force in order to check all possible paths. How we can do that? Please suggest a pseudo code and tell me the complexity of that algorithm.

If there are optimizations, then that would be awesome!

Answer 1

A naïvem approach could run through all possible vertex permutations.

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

The longest of such paths is your answer.

---

Or, you could do pretty much the same using 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

Time complexity is horrible O(N * N^N).