Shortest Path

Given an undirected, unweighted graph, return the length (number of edges) of the shortest path between src and dst. If they aren't connected, return -1.

shortestPath(graph, src, dst)

Input format: edges | src | dst, edges as a,b pairs (undirected).

Examples

edges w,x x,y z,y z,v w,v, src w, dst z   // → 2   (w – v – z)
edges a,c a,b c,b c,d b,d e,d e,c, src a, dst e   // → 2
edges a,b, src a, dst c                    // → -1

Walkthrough

Why depth-first search is the wrong tool here

Earlier problems used DFS for yes/no reachability — it doesn't matter which path it finds, only that one exists. But this asks for the shortest path, and DFS dives as deep as possible down one branch before backtracking — it might find a long, winding route to dst long before a shorter one. No guarantee the first path DFS finds is shortest.

The key idea: search in expanding rings of distance

You want a search that explores everything at distance 1 before anything at distance 2, all of distance 2 before distance 3, and so on — like ripples expanding outward. Searching this way, the first time you reach dst is guaranteed via the fewest edges, since every closer possibility was already exhausted.

This "explore everything at the current distance before moving further out" strategy is breadth-first search. Instead of a stack-like recursive dive, BFS uses a queue: process nodes in discovery order, which naturally produces the ring-by-ring expansion.

Building the approach

Start a queue with just the source, tagged distance 0.
Repeatedly take the earliest-added node out. If it's the destination, its tagged distance is the answer — BFS guarantees this is the first, and therefore shortest, arrival.
Otherwise, for each unseen neighbour, tag it with one more than the current distance, and add it to the back of the queue.
Mark nodes visited the moment you enqueue them, not when you dequeue — this prevents the same node being added multiple times through different paths.
If the queue empties without reaching dst, there's no path — return -1.

Why marking visited at enqueue time matters

If you waited until dequeue to mark a node visited, it could be pushed onto the queue multiple times by different neighbours before being processed, wasting work and risking the wrong distance depending on processing order. Marking at enqueue time guarantees each node gets its true shortest distance, exactly once.

This BFS-for-shortest-paths pattern is standard for any unweighted shortest-path question, including grids, where each cell is a node and its four orthogonal neighbours are its edges.

main.py

Auto-saved

Console

Press Run to execute your code, or Submit to test and complete this problem.