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

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.

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.

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

Quote:

---

Originally Posted by blackslither

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

---