# The Shortest Route

> Fewer hops is always better.

Canonical URL: <https://datadriven.io/problems/the_shortest_route>

Domain: Python · Difficulty: medium · Seniority: L4

## Problem

Given a directed graph as adjacency list dict, and two node names, return the minimum number of edges from start to end, or -1 if unreachable.

## Worked solution and explanation

### Why this problem exists in real interviews

This tests **BFS on an unweighted graph**, the standard algorithm for shortest path when all edges have equal weight. It probes graph traversal fundamentals, queue usage, and visited-set management.

> **Trick to Solving**
>
> BFS guarantees that the first time you reach a node, you have found the shortest path to it. Use a queue of `(node, distance)` pairs and a visited set to avoid cycles.

---

### Break down the requirements

#### Step 1: Initialize BFS from the start node

Enqueue the start node with distance 0. Mark it as visited immediately.

#### Step 2: Process neighbors level by level

For each node dequeued, check all neighbors. If a neighbor is the target, return `distance + 1`. Otherwise, enqueue unvisited neighbors.

#### Step 3: Return -1 if the queue empties without finding the target

An empty queue means all reachable nodes have been visited and the target is not among them.

---

### The solution

**BFS with distance tracking**

```python
from collections import deque
def shortest_path(graph: dict, start: str, end: str) -> int:
    if start == end:
        return 0
    visited = set()
    visited.add(start)
    queue = deque()
    queue.append((start, 0))
    while queue:
        node, dist = queue.popleft()
        for neighbor in graph.get(node, []):
            if neighbor == end:
                return dist + 1
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, dist + 1))
    return -1
```

> **Time and Space Complexity**
>
> **Time:** O(V + E) where V is the number of nodes and E is the number of edges. Each node and edge is visited at most once.
> 
> **Space:** O(V) for the visited set and queue.

> **Interviewers Watch For**
>
> Adding to visited when enqueueing (not when dequeueing) is critical. The dequeue-time check causes duplicate entries and wastes time. This is a subtle but important BFS detail.

> **Common Pitfall**
>
> Using DFS instead of BFS. DFS finds a path but not necessarily the shortest one. BFS is the correct choice for unweighted shortest paths.

---

## Common follow-up questions

- How would you modify this for weighted edges? _(Tests knowledge of Dijkstra's algorithm with a priority queue.)_
- What if you needed to return the actual path, not just the distance? _(Tests tracking parent pointers and reconstructing the path.)_
- How does this scale to a graph with millions of nodes? _(Tests awareness of memory constraints and bidirectional BFS optimization.)_

## Related

- [All practice problems](https://datadriven.io/problems)
- [Mock interview mode](https://datadriven.io/interview/the_shortest_route)
- [Python Interview Questions](https://datadriven.io/python-interview-questions)
- [Data Engineering Interview Prep Guide](https://datadriven.io/data-engineer-interview-prep)
- [Daily Challenge](https://datadriven.io/daily)

---

Source: DataDriven (https://datadriven.io). 100% free data engineering interview prep. Live code execution against Postgres 16, Python 3.11, and Spark sandboxes. No paywall, no premium tier, no signup gate.