Finding a path with minimum cost and maximum length at maximum cost

Question

I am looking for an algorithm to find the path between two nodes with a minimum cost and a maximum length, given the maximum cost in a non-oriented weighted full graph. Weights are not negative.

I am currently using DFS and it is rather slow (lots of nodes and maximum length too). I already discard all impossible nodes in each DFS iteration.

Can someone point me to a well-known algorithm to better handle this problem?

To clarify: ideally, the algorithm should look for a path to the minimum cost, but it is allowed to add value if it means visiting more nodes. This should end when he concludes that it is impossible to reach more than n nodes without crossing the cost constraint, and it is impossible to reach n nodes with less cost.

Update

Graph example. We need to go from A to B. To limit costs, the value is set to 5:

This path is (red) approved, but the algorithm should continue to search 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 is much better than before, and the cost is acceptable 5

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

Images of hope better explain text

Answer 1

Idea 1:

In my opinion, your problem is a variation of pareto the optimal shortest path finding problem. Since you are referring to 2 different optimality indicators:

• The longest path by the number of faces
• The shortest path over the edge mass

Of course, some side restrictions just complicate the task.

For optimal Pareto results, you need to implement many dijkstra criteria. For this problem, I found two promising articles:

• Multicriteria Pareto Optimal Path Algorithm
• In the multicriteria shortest problem

Unfortunately, I could not find pdf files for these papers and articles that I read earlier, where in German :( Nevertheless, this should be your entry point and lead you to an algorithm to solve your problem nicely and smoothly.

Idea 2:

Another way to solve this problem may be to calculate the hamilton path , since the longest path in the full schedule is really a hamiltonian path. After calculating all this path, you still have to find the one with the minimum total cost of the edge. This scenario is useful if the path length in each case is more relevant than the cost.

Idea 3:

If the cost of the ribs is a more important fact, you should calculate all the paths between these two nodes of a given maximum length and look for the one with the most used ribs.

Output:

I think that the best results will be obtained using idea 1. But I did not know your scenario well, so other ideas might be option two.