Weight Constraint Path: Shortest Path in a Graph Where Edge Traversal Has Weight Limits

Question

## Problem

You have a directed weighted graph of `n` nodes. Each edge has a distance and a maximum weight capacity. You are transporting a package of weight `w`. Find the shortest path from source `s` to destination `d` such that every edge on the path can support at least weight `w`. If no valid path exists, return -1.

```python
def shortest_valid_path(
    n: int,
    edges: list[tuple[int, int, int, int]],  # (u, v, distance, max_weight)
    s: int,
    d: int,
    w: int
) -> int:
    pass
```

**Example:**
```
n=4, edges=[(0,1,4,10),(0,2,2,5),(2,3,3,10),(1,3,1,10)], s=0, d=3, w=8
Valid edges (capacity>=8): (0,1,4,10),(2,3,3,10),(1,3,1,10)
Shortest valid path: 0->1->3 = distance 5
Output: 5
```

## Follow-ups

1. Can you reduce this to a standard Dijkstra problem? What transformation do you apply?
2. What if you want the path with the maximum minimum edge capacity (widest path problem)?
3. If edge capacities degrade over time, how would you model that?
4. How does the complexity change if you must find the top-3 shortest valid paths?

Weight Constraint Path: Shortest Path in a Graph Where Edge Traversal Has Weight Limits

Question Details

Full Details

Topics

More from Uber