Optimal Commute Path: Shortest Path with Time-Dependent Edge Weights

Question

## Problem

You are given a city graph where edges represent roads. Each road has a base travel time, but also a `congestion_factor(hour)` function that multiplies the base time during rush hours. Given a start node, an end node, and a departure hour, find the minimum total travel time path.

```python
def optimal_commute(
    n: int,                          # number of nodes
    edges: list[tuple[int,int,int]], # (u, v, base_time)
    congestion: dict[tuple[int,int], callable],  # (u,v) -> f(hour) multiplier
    start: int,
    end: int,
    departure_hour: int
) -> tuple[int, list[int]]:
    """Returns (total_time, path)."""
    ...
```

```
Edge A->B: base=10, congestion at hour 8: 2x -> effective=20
Edge A->C: base=15, congestion at hour 8: 1x -> effective=15
Edge C->B: base=3,  congestion at hour 8: 1x -> effective=3

departure_hour=8, start=A, end=B:
  A->B direct: 20
  A->C->B: 15+3=18  <- optimal
Output: (18, [A, C, B])
```

## Follow-ups

1. The hour changes as you travel (a long route might cross into a new hour). How do you model time-dependent weights in Dijkstra?
2. What if you want the route that minimizes worst-case time across all possible congestion scenarios?
3. How would you precompute shortest paths for all (start, end, hour) pairs to serve real-time queries?
4. Describe how you would test this system with realistic traffic data.

Optimal Commute Path: Shortest Path with Time-Dependent Edge Weights

Question Details

Full Details

Topics

More from Databricks