City Path: Find the Shortest Path Between Cities in a Weighted Graph

Question

## Problem

You are given a list of roads between cities, each with a travel time. Find the minimum time to travel from a source city to a destination city. If no path exists, return -1.

```python
from typing import List, Dict

def shortest_path(
    n: int,
    roads: List[List[int]],
    source: int,
    destination: int
) -> int:
    # n: number of cities (0-indexed)
    # roads: [[city_a, city_b, travel_time], ...] (undirected)
    # return: minimum travel time, or -1 if unreachable
    pass
```

**Example:**
```
n = 4
roads = [[0,1,4],[0,2,1],[2,1,2],[1,3,1]]
source = 0, destination = 3

Shortest: 0->2->1->3, cost = 1+2+1 = 4
Output: 4
```

## Approach

Dijkstra's algorithm with a min-heap. Time: O((V + E) log V).

## Follow-ups

1. What changes if roads are directed (one-way)?
2. How would you handle negative edge weights? What algorithm applies?
3. If you need to find the shortest path that passes through a required intermediate city, how do you modify the approach?
4. How would you return the actual path (list of cities) in addition to the cost?

City Path: Find the Shortest Path Between Cities in a Weighted Graph

Question Details

Full Details

Topics

More from Snowflake