CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 2 of 2

Thread: Longest path

  1. #1
    Join Date
    Jun 2013
    Posts
    1

    Smile Longest path

    Hey guys!

    I've read a little about finding the longest path in undirected graph, but haven't found any solutions to that problem. So let's assume we have undirected, unweighted graph - how do we determine the longest possible path, where each node can be visited only once?

    As far as I understood, this is NP-complete problem, but do you guys know the algorithm to solve it?

  2. #2
    Join Date
    Jul 2013
    Posts
    576

    Re: Longest path

    Quote Originally Posted by Donutto View Post
    As far as I understood, this is NP-complete problem, but do you guys know the algorithm to solve it?
    You can always use brute force and make an exhaustive search.

    You start at each of the N nodes. From each of them you can reach at most N-1 not yet visited nodes. And from each of those you can reach at most N-2 unvisited nodes. Etcetera. Sooner or later you will reach a node from where no further nodes can be reached. That's the end of one path. If this path contains N nodes no other path can be longer. If there are fewer nodes in the path the search must continue because there may be longer paths.

    To implement solutions like this recursion is often used. The complexity will be something like O(N!) so it's not very efficient but if there are few edges in the graph it can still be pretty fast.
    Last edited by razzle; July 23rd, 2013 at 01:59 AM.

Tags for this Thread

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  





Click Here to Expand Forum to Full Width

Featured