Shortest path algorithm with a maximum number of edges limit

[blackslither]

Hi

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

i've found shortest path algorithms but not with a number of edges limit , and i've tried to modify A* , Bellman-Ford algorithms but without success .

i need an algorithm that has the limit embedded .

10x

Happy Holiday

[Murtan]

Are you saying that you want an algorithm that will return longer paths if the shortest path has too many edges?

Is the longer path likely to have fewer edges?

[blackslither]

Are you saying that you want an algorithm that will return longer paths if the shortest path has too many edges?

Is the longer path likely to have fewer edges?

every edge has a cost , i want the path with the minum cost that has at most N edges . So if a path has 7 edges and cost 60 , and another path has 5 edges and cost 66 ., and the limit N=6 . The shortest path is the one with the cost 66 , because the one wioth the cost 60 is a edge too much .

[Murtan]

So its not really a shortest path, its a 'cheapest' path, but with an edge limit.

Something along the line of the travel agent telling you that you can save $20 by connecting through 5 cities -- you'd rather spend the $20 and save the stops.

I haven't looked at the A* algorithm in detail and I don't recall Bellman-Ford. Logically, it would seem to be fairly straightforward to either short-circuit the search to fail a path when it exceeds the specified length, or to 'modify the cost' of edges beyond the limit to make them appear cost prohibitive. Though if the algorithms are doing other work to minimize the amount of work to be done I guess it could be harder to 'make it fit'.

So the given data for the problem is:

1. The list of nodes
2. The edges (connections between nodes) and their costs
3. The maximum number of edges (N)
4. The starting node
5. The ending node

Is it possible that there may be a 'no solution'? (If N was sufficiently low, there might be no path that has fewer than N edges.)

I found a couple of links to an algorithm that looks like you could modify to not only track the 'cost' but also the number of edges consumed to get there and just 'not visit' (don't look for more paths from) nodes that it already takes N edges to reach:

Dijkstra Shortest Path Algorithm or Shortest Path

[BestJewSinceJC]

Dijkstra's algorithm would not be easy to modify, I don't think. . if you do the algorithm on paper, you end up with a 'trail' of visited Nodes in your shortest path. This means that when you program it, you're essentially keeping track of each Node on the shortest path. But if I remember correctly, you're not keeping track of anything else: for example, alternate paths. So you'd have to rewrite the entire algorithm in order to make it consider your edge limit, making it useless.

[Murtan]

After looking at it some more, the idea I proposed (of just refusing to visit or process nodes if they would lead to a too many edges solution) could be 'led astray' with the right structure.

If there was route to the endpoint that was one edge too long, and a way to get to one of the intermediate points at a higer cost, but lower edge count, the algorithm would not ever see that lower edge, but higher cost path.

Thus the solution I proposed is flawed in that it would report a 'no solution' in the case of the example above. (If there were no other routes.)

[BestJewSinceJC]

And my point is that Dijkstra's algorithm does not *know* how many edges are on the path until it is finished, so modifying it would not make sense. Am I wrong?

[Murtan]

You could modify it to keep more of the information as it went, but I'm not sure about how to get it to backtrack.

The base algorithm tracks for each target node in the system:

• Has the node been processed (visited)
• current least cost to get here
• parent (or predecessor) on current least cost path

Arranged in a table of sorts. It initializes the table with the costs to get from the starting node to the nodes it can reach directly.

Then it loops, processing the lowest cost unprocessed node in the table until it reaches the destination node at the least cost.

This looks like it works really well, but does not support the requested edge limiting.

If we modified the information we keep as we go to include the length of the path and the previously found, something like this:

• Has the node been processed (visited)
• List of Routing Info:
  • edges to here
  • cost to here
  • previous node

We would have all the information required to solve the problem.
But I'm still not sure how to get the algorithm to 'backtrack' and try another route.

The only other method I come up with is an exhaustive search of all paths that meet the edge requirement. We could use something like Dijkstra's 'traveling' to find all possible paths from the start to the destination that meet the edge limit. We could either then price the routes as we go or on a second pass and report the lowest cost.

We should be able to do a little optimization of cases as we go. For each node X (which I propose to mean any intermediate node) the only possible routes of interest are the lowest cost routes for a given edge count.