Using Dijkstra's algorithm to find a 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 at one node, and stop at another node which is the last location. Now here comes the problem:

Visualize the problem. The edges are roads, and the edge weights are the max weight limits for vehicles driving on the roads. We would like to drive the biggest truck possible from A to F. I want the largest maximum allowed weight for all paths from A to F.

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

Answer 1

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

The idea behind the algorithm is to run Dijkstra's algorithm with a twist. Normally, when running Dijkstra's algorithm, you keep track of the length of the shortest path to each node. In the modified Dijkstra's algorithm, you instead store, for each node, the maximum possible value of a minimum-weight edge on any path that reaches the node. In other words, normally in Dijkstra's algorithm you determine which edge to expand by finding the edge that maximizes the quantity

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

Where s is the start node, u is some node you've explored so far, and (u, v) is an edge. In the modified Dijkstra's, you instead find the edge minimizing

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

That is, you consider the bottleneck edge on the path from the source node to any node you've seen so far and consider what bottleneck path would be formed if you left that node and went some place else. This is the best bottleneck path to the target node, and you can repeat this process.

This variant of Dijkstra's algorithm also runs in O(m + n log n) time using a good priority queue. For more information, consider looking into these lecture slides that have a brief discussion of the algorithm.

Interestingly, this is a well-known problem that's used as a subroutine in many algorithms. For example, one of the early polynomial-time algorithms for solving the maximum flow problem uses this algorithm as a subroutine. For details about how, check out these lecture notes.

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

Answer 2

No Dijkstra, no flow problem. It's a lot easier: Just use your favorite graph search (BFS or DFS).

Instead of computing & tracking the cost associated with reaching a certain node in the graph, just compute the 'size' of the biggest truck that is allowed to use this path (the minimum of weights of all edges in the path). When multiple search paths meet in a node throw away the path that has the lower 'truck weight limit'.