Finding the shortest path in a weighted directed multigraph with additional constraints
Given a weighted directed multigraph, I have to find the shortest path between the starting vertex u and the vertex v. Besides weight, each edge also has time. The path connecting u and v cannot take longer than the specified maximum time. The problem with using Djikstra, chances are the shortest path takes longer than the limit.
My approach is to find all valid paths between u and v and minimize the weight. But this approach is impractical due to its high complexity.
Any ideas?
source to share
If the weights are small enough
In this case, what you can do for each node, store all possible sums of weights that you can get along the way to that node. Now you can do dijsktra on this new graph and try to minimize the time across nodes that are pairs (node, weight_sum).
If times are short enough
You can do the same as in the previous example, but on (node, time) pairs.
a common problem
I am afraid that in general all you can do is try every possible way, try to improve it with adventure.
source to share