PPractick

The problem

A metro map is an undirected graph where every hop between adjacent stations takes the same time. For a given source station, the app shows the minimum number of hops to every station, or −1 if a station can't be reached. With equal edge weights, BFS is the shortest-path algorithm. It discovers vertices in order of their distance, so the first time a station is reached, its distance is final.

Example: 9 stations, source 0 → [0, 1, 2, 1, 2, 3, 3, 4, 4].

Function signature

vector<int> shortestPath(int n, const vector<pair<int, int>>& edges, int src);  // -1 if unreachable

Test cases

Input (n, edges, src)	Output	Explanation
(9, [[0,1],[0,3],[3,4],[4,5],[5,6],[1,2],[2,6],[6,7],[7,8],[6,8]], 0)	[0, 1, 2, 1, 2, 3, 3, 4, 4]
(5, [[0,1],[0,2],[1,3],[2,3],[3,4]], 4)	[3, 2, 2, 1, 0]
(4, [[0,1],[1,2]], 0)	[0, 1, 2, -1]	3 is unreachable
(3, [], 1)	[-1, 0, -1]
(1, [], 0)	[0]

(Confirm: undirected edges, all of weight 1; unreachable vertices get −1.)

How interviewers phrase it

• "Given an undirected graph with unit weights, find the shortest path from the source to all other vertices; −1 if unreachable" (GeeksforGeeks "Shortest path in Undirected Graph having unit distance").

Clarifying questions to ask

1. Are all edges weight 1? (Yes, which makes BFS enough.)
2. What should unreachable vertices get? (−1.)
3. Directed or undirected? (Undirected; BFS works for both.)

Follow-ups to expect

1. "Why is BFS correct here?"
2. "Why not Dijkstra?"
3. "What if weights are 0 or 1?"
4. "How do you recover the path itself?"
5. "Complexity?"

Related questions

• Cycle Detection in Undirected Graph (bfs) Hard
• Word ladder I Hard
• Word ladder II Hard
• Topological sort or Kahn's algorithm Hard
• Alien Dictionary Hard
• Shortest Distance in a Binary Maze Hard

All 474 dsa interview questions

DSA mock interviews · System design interview questions · Free mock interview practice · Browse interviewers · Sign in