1. Overview

In this tutorial, we’ll explain the maximum-minimum path capacity problem in graph theory. We’ll define what it is, how to solve it, and how the solution differs from Dijkstra’s.

2. Defining the Problem

The maximum-minimum path capacity problem deals with weighted graphs.

We consider the weight of each edge to represent that edge’s capacity. Our task is to find the path that starts from a source node source and ends at a goal node goal inside the graph. The edge with the lowest capacity in a path forms that path’s capacity.

Among all the paths from source to goal, what we want to do is find the path of maximum capacity.

As a practical example, suppose the graph represents the capacity of water that each pipe can deliver per second. Obviously, we’d be looking for a path that can deliver the largest amount of water per second, and we can’t deliver it any faster than the smallest pipe in the path.

3. Example

Have a look at the following example. We consider the source node to be S and the goal node to be G.

From the graph example, we see that there are multiple paths connecting node S with G. The following table lists the different paths along with their capacity.

Rendered by QuickLaTeX.com

Out of all the paths, path number 3 has the largest capacity, which is 4. Therefore, the maximum-minimum capacity for the given graph equals 4.

4. Algorithm

In order to solve this problem, we’ll use a modified version of Dijkstra’s algorithm.

4.1. Differences From Dijkstra’s Algorithm

The pseudocode of this problem is mostly derived from Dijkstra’s algorithm with the following changes:

  • Instead of having a distance array, we’ll have an array called capacity. This array will store the maximum capacity of each node. By the maximum capacity of a node, we mean the maximum-minimum capacity for all the paths from source to this node.
  • In Dijkstra’s algorithm, we initialize each node’s distance with \infty.
    • For the slot for source, we still do this, indicating that the source node has an unlimited capacity to itself.
    • However, for the remaining slots, we’ll initialize the capacity array with -\infty, corresponding to the worst case.
  • In this problem, when visiting the neighbors of some node, the concept of updating the capacity of a neighboring node is different from the one in Dijkstra’s algorithm. In our case, we update the capacity of each neighboring node with the maximum value among the previous value, the capacity of the node that got us to this neighboring node, and the capacity of the edge we just crossed. Also, we’ll need to update this neighboring node’s capacity inside the data structure we use.
  • In each step, rather than choosing the node with the lowest cost, we’ll choose the node with the largest capacity.

The proof of this algorithm’s optimality is that we always process the node with the largest capacity. Hence, when we reach the goal node, all the remaining nodes inside the data structure must have a smaller capacity. Therefore, the found path would be the one with the maximum-minimum capacity.

4.2. Pseudocode

Now, let’s review the algorithm in pseudocode:

Rendered by QuickLaTeX.com

First, we initialize the capacity array with -\infty. We’ll also initialize an array prev which will store, for each node u, the node that gets us to reach node u with the maximum path capacity.

Next, we initialize the capacity of the source node with \infty and add all the nodes to Q. The purpose of Q is to find the node with the maximum capacity so far quickly. Also, Q needs to support updating the capacity of some node through the function update. For this, we can use a set that stores the node with its capacity sorted in descending order based on the capacity.

In each step, we extract the node with the maximum path capacity from Q using the function getNodeWithMaxCapacity. If the extracted node has a capacity equal to -\infty, then all the remaining nodes inside Q can’t be reached from source node. Therefore, we can just stop processing further nodes.

Otherwise, we iterate over all the neighbors of node u. for each neighbor, we calculate the new capacity. The new capacity is the minimum between the capacity of node u and the capacity of the edge between u and v. Therefore, we’ve taken the minimum capacity along the path.

After that, we compare the new capacity to the old one for node v. If the new capacity is better, then we update the information of node v with the new capacity. Updating the information of node v includes updating its capacity, updating the prev value for it to become u, and using the function update that removes this node’s object from Q and adds it again with the new path capacity.

Finally, we return capacity, which is the calculated capacity.

The algorithm can be implemented to have a complexity of O(E \cdot log(V)), similar to Dijkstra’s algorithm, where E is the number of edges inside the graph and V is the number of vertices.

4.3. Finding the Path

We’ll use the prev array to restore the path we need. Let’s take a look at the algorithm:

Rendered by QuickLaTeX.com

The algorithm is simple. We start from the goal node. In each step, we add the current node to the path. Also, we move one step back to the previous node using the prev array calculated in findMaxMin function.

Since the source node will have its previous node equal to undefined, we can stop going back once we reach the undefined value.

The complexity of this algorithm (without the findMaxMin function) is O(V), where V is the total number of vertices inside the graph.

5. Conclusion

In this tutorial, we presented the maximum-minimum capacity in a graph problem. First, we defined the problem. Next, we provided an example that better explains the concept.

After that, we highlighted the main differences between our algorithm and Dijkstra’s algorithm.

Finally, we showed the algorithm.

Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments