6

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!

Narek
  • 38,779
  • 79
  • 233
  • 389
  • 2
    You have to put extra constraints. Otherwise the path is infinite... – hivert Feb 19 '14 at 12:29
  • 2
    Each vertex is included in the path only ones - is a simple path. – Narek Feb 19 '14 at 12:34
  • 1
    Just because it's NP-complete doesn't mean you should use brute force. Sure, you can't (as far as known) do better than exponential time in the worst case, but worst cases are rare and to give a couple of examples, 3-SAT instances with thousands of clauses and variables and TSP instances with thousands of cities are routinely solved, clearly not with brute force. – harold Feb 19 '14 at 13:06
  • unweighted: https://stackoverflow.com/questions/2525316/longest-acyclic-path-in-a-directed-unweighted-graph – Ciro Santilli OurBigBook.com Nov 13 '17 at 16:21

2 Answers2

6

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).

AlexD
  • 32,156
  • 3
  • 71
  • 65
  • This is the trivial brute-force solution. – Bas Swinckels Feb 19 '14 at 12:48
  • Fine what about modifying DFS for doing this brute-force? – Narek Feb 19 '14 at 13:53
  • 1
    @BasSwinckels Sure. But the question says: "we should do Brute Force in order to check all possible paths. How we can do that?". So it sounded to me that brute force is OK. – AlexD Feb 19 '14 at 13:54
  • @Narek What do you mean exactly? For any vertex `R` we can construct a tree where `R` is the root and the number of *levels* in the tree is (less or) equal to the number of vertices in our graph. Every leaf corresponds to a different path then, and we need to find the farthermost one. – AlexD Feb 19 '14 at 14:06
  • 1
    @Narek I updated my answer. Basically, it is very much DFS-ish approach, without building the tree explicitly. – AlexD Feb 19 '14 at 17:21
  • @AlexD what a pity you deleted your first message. This one and the one you have written before were valuable. Thanks for your help. – Narek Feb 20 '14 at 06:52
  • This solution is so not intuitive. It is very similar to DFS, but slightly different, and I don't feel the difference, why this one in not a DFS, but brute-force :) – Narek Feb 20 '14 at 06:58
  • Event not sure that this works. :( Is there something that I can read about this solution, or this is just your solution - you have invented :) – Narek Feb 20 '14 at 07:15
  • let us [continue this discussion in chat](http://chat.stackoverflow.com/rooms/47938/discussion-between-alexd-and-narek) – AlexD Feb 20 '14 at 11:35
  • That's n^3 not n*n^n – CME64 Jun 03 '19 at 17:53
  • @CME64 Would not it mean that a NP-hard problem was solved in polynomial time )? – AlexD Jun 25 '19 at 00:42
  • @AlexD "A common misconception is that the NP in "NP-hard" stands for "non-polynomial" when in fact it stands for "non-deterministic polynomial acceptable problems". Although it is suspected that there are no polynomial-time algorithms for NP-hard problems, this has not been proven. Moreover, the class P, in which all problems can be solved in polynomial time, is contained in the NP class." Source: wikipedia – CME64 Jun 27 '19 at 06:45
4

If your graph is a special case in which it's directed and acyclic, you could do a dynamic programming approach such as the one described here. You basically sort your graph topologically, then in the topological order, for every node V, you check all its neighbors and update their "distance" value if it's bigger than the "distance" already memorized (initialized with -infinity or something).

Otherwise, in the general case, the problem is indeed NP-complete as it reduces to the Hamiltonian cycle. One thing you could do is negate all the edges and try the Bellman-Ford Algorithm. Beware that it's not good for negative cycles, however.

webuster
  • 2,490
  • 18
  • 27