Find path with minimum cost and maximum length given a maximum cost

Question

I'm searching for an algorithm to find a path between two nodes with minimum cost and maximum length given a maximum cost in an undirected weighted complete graph. Weights are non negative.

As I stand now I'm using DFS, and it's pretty slow (high number of nodes and maximum length too). I already discard all the impossible nodes in every iteration of the DFS.

Could someone point me to a known algorithm for better handling of this problem?

To clarify: ideally the algorithm should search for the path of minimum cost, but is allowed to add cost if this means visiting more nodes. It should end when it concludes that it's impossible to reach more than n nodes without crossing the cost limit and it's impossible to reach n nodes with less cost.

Update

Example of a graph. We have to go from A to B. Cost limit is set to 5:

This path (in red) is ok, but the algorithm should continue searching for better solutions

This is better because although the cost is increased to 4, it contains 1 more node

Here the path contains 3 nodes so it's a lot better than before and the cost is an acceptable 5

Finally this solution is even better because the path also contains 3 nodes but with cost 4, with is less than before.

Hope images explain better than text

Answer 1

Idea 1:

In my opinion your problem is a variation of the pareto optimal shortest path search problem. Because you refer to 2 different optimality metrics:

1. Longest Path by edge count
2. Shortest Path by edge weight

Of course some side constraints just make the problem more easy to calculate.

You have to implement a multi criteria dijkstra for pareto optimal results. I found two promising paper in english for this problem:

• A multicriteria Pareto-optimal path algorithm
• On a multicriteria shortest path problem

Unfortunately I wasn't able to find the pdf files for those papers and the papers I read before where in german :( Nevertheless this should be your entry point and will lead you to an algorithm to solve your problem nice and smoothly.

Idea 2:

Another way to solve this problem could lie in the calculation of hamilton path, because the longest path in a complete graph is indeed the hamilton path. After calculation of all such path you still have to find the one with the smallest total edge weight cost. This scenario is useful if the length of the path is in every case more relevant than the cost.

Idea 3:

If the cost of the edges is the more important fact you should calculate all paths between those two nodes of a given maximum length and search for the one with the most used edges.

Conclusion:

I think the best results will be obtained by using idea 1. But I didn't know your scenario to well, therefore the other ideas might be an option two.