Thread: Shortest path algorithm with a maximum number of edges limit

  1. #1
    Registered User
    Join Date
    Oct 2008
    Posts
    4

    Shortest path algorithm with a maximum number of edges limit

    Hi

    I'm looking for a "shortest path algorithm" in a graph , but with a maximum number of edges limit . So the path has to contain at most N edges .

    10x

    Happy Holiday

  2. #2
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    Shortest weighted path, I guess? (Otherwise there wouldn't be a problem -- just find the shortest path and if it's too long throw it away.) If so, I would guess you would want to add another tag to your node that says how many steps you've taken, and not allow yourself to take a step if it's too many.

    I haven't sat down with a piece of paper and worked it out, but you may also have to allow yourself multiple tags on the same node (add another tag to a node when you have a more expensive path, but with strictly fewer steps, so it may survive farther than the other one), instead of trying to fill the normal way and resetting when it all goes pear-shaped. You'll still be able to go backwards when building your answer, since only one tag will have the right number of steps in it.

  3. #3
    Ugly C Lover audinue's Avatar
    Join Date
    Jun 2008
    Location
    Indonesia
    Posts
    489
    You may already read:
    http://en.wikipedia.org/wiki/Shortest_path_problem

    And I think you'll need to add a counter (in parameter) and check the limit in your recursive search function.

    A little suggestion: Don't forget to check whether the current node is your first node or not in your function, otherwise it will be infinite loop.
    Just GET it OFF out my mind!!

  4. #4
    Registered User
    Join Date
    Oct 2008
    Posts
    1,262
    The best algorithm here depends on several things. The minimum, average and maximum size of the graphs. The min, avg, max number of edges. The min, avg, max number of max edges you want. Are the weights possibly negative or not?

    The easiest but quite efficient algorithm is probably Dijkstra, where you don't store whether you visited a node, but whether you visited a node with the current number of steps.
    If the weights can be negative, you can not use Dijkstra...

  5. #5
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396
    Quote Originally Posted by blackslither View Post
    Hi

    I'm looking for a "shortest path algorithm" in a graph , but with a maximum number of edges limit . So the path has to contain at most N edges .

    10x

    Happy Holiday
    Code:
    Find the shortest path.
    If the length of this path is greater than MaxPath:
      Fail
    Else:
      Success
    Code:
    //try
    //{
    	if (a) do { f( b); } while(1);
    	else   do { f(!b); } while(1);
    //}

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. hi need help with credit limit program
    By vaio256 in forum C++ Programming
    Replies: 4
    Last Post: 04-01-2003, 12:23 AM
  2. Rsa Algorithm
    By Unregistered in forum C++ Programming
    Replies: 2
    Last Post: 03-31-2002, 08:29 AM
  3. prime number algorithm
    By Unregistered in forum C++ Programming
    Replies: 12
    Last Post: 02-22-2002, 11:30 PM
  4. Random Number problem in number guessing game...
    By -leech- in forum Windows Programming
    Replies: 8
    Last Post: 01-15-2002, 05:00 PM
  5. Array of boolean
    By DMaxJ in forum C++ Programming
    Replies: 11
    Last Post: 10-25-2001, 11:45 PM