Find path with minimum cost and maximum length given a maximum cost
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:
- Longest Path by edge count
- 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.