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

1 answer

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.



All Articles