Search for the fastest way that does not exceed the specified cost

Question

I had a problem finding the fastest path that does not exceed a given cost.

Let's say I have the indicated maximum cost and 4 entries.

// specified cost 10 // end point 5 //(start point) (finish point) (time) (cost) 2 5 50 5 3 5 20 9 1 2 30 5 1 3 30 7 

I have to decide whether it is possible to get from point (1) to (5) (it is impossible when there is no path that is <= what we have, or when there is no connection between 1-5) and if so, what will be the most quick way to get there.

The output for such data will be:

 80 // fastest time 3 1 // number of points that (1 -> 2) -> (2 -> 5) 

Keep in mind that if there is a record that you can move 1-> 2

 1 2 30 5 

This does not allow you to move 2 <-1 .

Answer 1

Use dynamic programming, something like this:

 Route(node, length, target, accumulated) if length <= 0 return -1 if node == target return accumulated For each adjacent node: current length = accumulated + Route(adjacent node, length - connecting edge weight, target, accumulated + connecting edge weight) min length = min(current length, min length) return min length 

Answer 2

A web search finds http://www.cs.elte.hu/~alpar/publications/jour/AKCE_October_25.pdf , suggesting that this is a fairly relevant research issue. Without reading the document, my approach would be to use dynamic programming, where for each node you save a record of the shortest path with a cost <= K for every reasonable K. You only need to save the values ​​of K, where the shortest available path changes with K. This may be feasible if either the cost or the time were reliably small integers. If not, you can create examples of problems that require computing and saving uncontrollable numbers of partial solutions.