Using Dijkstra's algorithm to find the path that can carry the most weight

Question

I have a graph with X nodes and Y edges. Weighted edges. The point is to start from one node and stop at another node, which is the last. Now the problem is:

Visualize the problem. Edges are roads and maximum weights are maximum weight limits for vehicles on roads. We would like to drive the largest truck from A to F. I want the largest maximum allowable weight for all tracks from A to F.

Can I use some Dijkstra algorithm for this problem? I am not sure how to express this problem in the form of an algorithm that I can implement. Any help is much appreciated. I got confused because Dijkstra's algorithm just looks only for the shortest path.

Answer 1

If I understand correctly, you want to find the path between some nodes with the maximum edge of the bottleneck. That is, you need a path whose smallest edge is as large as possible. If this is what you want to solve, then there is a very simple modification of the Dijkstra algorithm that can be used to solve the problem.

The idea of ​​the algorithm is to run Dijkstra's algorithm with a twist. Typically, when you run the Dijkstra algorithm, you track the length of the shortest path for each node. In the Dijkstra's modified algorithm, you instead save for each node the maximum possible edge value of the minimum weight along any path that reaches the node. In other words, usually in the Dijkstra's algorithm you determine which edge you want to expand to, finding the edge that maximizes

d (s, u) + l (u, v)

Where s is the beginning of a node, u is some node that you have studied so far, and (u, v) is an edge. In the modified Dijkstra, you will instead find a minimizing rib

min (bottleneck (s, u), l (u, v))

That is, you are considering the edge of the bottleneck on the way from the source of the node to any node that you have seen so far, and think about which way the bottleneck will be formed if you leave this node and go to some other place. This is the best bottleneck path to a node target, and you can repeat this process.

This version of Dijkstra's algorithm also runs in O (m + n log n) time using a good priority queue. For more information, review these lecture slides , which provide a brief description of the algorithm.

Interestingly, this is a well-known problem used as a subroutine in many algorithms. For example, one of the earliest polynomial time algorithms uses this algorithm as a subroutine to solve the maximum flow problem. Learn more about how these notes are lectures .

Hope this helps! And if I misinterpreted your question, let me know so that I can delete / update this answer.

Answer 2

No Dijkstra, no flow problem. This is much simpler: just use your favorite schedule search (BFS or DFS).

Instead of calculating and tracking the costs associated with reaching a certain node graph on the graph, simply calculate the "size" of the largest truck that is allowed to use this path (the minimum weight of all the edges on the path). When multiple search paths occur in a node, drop the path that has the lower limit of the truck’s weight.

Answer 3

Here is a simple and effective way:

Let MAX be the maximum edge weight in the graph. Binary search 0 <= k <= MAX , which you can get from A to F using only edges with weights >= k . You can use the width of the first search to see if this is possible (don't take an edge if its weight is too small).

This gives the O((X + Y) log V) algorithm, where V is the range of your weights.

Answer 4

According to an algorithm like Dijkstra, this is an optimal substructure and a way to quickly calculate the objective value for a single path extension with a known objective value. Here, the optimal substructure means that if you have an optimal path from vertex x to another vertex y, then the subpath from x to the second or last vertex is optimal.

(Ivlad, I can get O (X + Y) with randomization.)