Maximum Bandwidth: Find the Path Between Two Nodes That Maximizes Minimum Edge Capacity

Question

## Problem

You have a network of `n` nodes and `m` weighted edges where edge weight represents bandwidth capacity. Find the maximum bandwidth achievable between a source node `s` and destination node `t`, defined as the maximum over all paths of the minimum edge capacity along that path.

```python
def max_bandwidth(n: int, edges: list[tuple[int,int,int]], s: int, t: int) -> int:
    # edges: (u, v, capacity)
    pass
```

**Example:**
```
n=4, edges=[(0,1,3),(1,2,1),(0,2,4),(2,3,2)], s=0, t=3
Paths: 0->1->2->3 bottleneck=1; 0->2->3 bottleneck=2
output -> 2
```

## Approach

Modified Dijkstra or Kruskal. With Kruskal: sort edges by capacity descending, union-find until s and t are connected -- that edge's capacity is the answer. O(m log m).

## Follow-ups
1. How does this differ from standard shortest-path? Which data structures change?
2. The graph has 10 million edges. What is the memory-efficient approach?
3. Edges now have both capacity and latency. Find the path maximizing bandwidth subject to latency <= L.
4. How does the answer change if you can split flow across multiple paths (max-flow)?

Maximum Bandwidth: Find the Path Between Two Nodes That Maximizes Minimum Edge Capacity

Question Details

Full Details

Topics

More from Sofi