Minimum Path Distance in Undirected Graph — Problem Statement & Solution Guide
Problem Description
Given an integer n representing the number of nodes labeled from 0 to n-1, and a 2D integer array edges where edges[i] = [ui, vi] represents an undirected edge between nodes ui and vi, return the minimum number of edges to traverse to reach a target node from a starting node. If no path exists between the start and target, return -1. Note that the start and target nodes must be integers between 0 and n-1.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Minimum Path Distance in Undirected Graph"
WHY DOES IT MATTER?
Shortest‑path in unweighted graphs is a foundational pattern that appears in networking (minimum hops), social networks (degrees of separation), and many interview problems that test graph traversal mastery.
OPTIMIZATION CHALLENGE
The key insight is to stop the search as soon as the target is dequeued from the BFS queue; this early exit prevents traversing the entire graph and reduces both time and memory usage.
REAL-WORLD CONNECTION
Think of a city’s subway map where each station is a node and each direct line is an edge; finding the fewest stops between two stations is exactly this problem, and BFS mimics a commuter checking all stations reachable in 1 stop, then 2 stops, and so on.
Always initialize a visited array (or set) before enqueuing the start node; forgetting this leads to cycles and infinite loops, especially in dense or self‑looping graphs.
COMPLEXITY AT A GLANCE
O(V + E)O(V)Core Theory — Why This Approach?
The problem asks for the shortest number of edges between two vertices in an undirected, unweighted graph. In such graphs, every edge contributes a uniform cost of one, which makes Breadth‑First Search (BFS) the optimal paradigm: BFS expands vertices in concentric layers, guaranteeing that the first time we encounter the target we have traversed the minimal number of edges. A naive approach would enumerate all possible paths (e.g., via depth‑first recursion) which leads to exponential blow‑up because the number of simple paths can be O(n!). Moreover, DFS does not respect edge‑weight uniformity and can easily miss the shortest route. The optimal solution leverages BFS combined with a visited set to avoid revisiting nodes, achieving linear time relative to the size of the graph (O(V+E)).
Interview Questions on This Problem
Q1How would you modify the BFS solution if each edge had a non‑negative weight and you needed the minimum total weight path?
Replace BFS with Dijkstra's algorithm using a min‑heap (priority queue). Each node stores the cumulative distance from the source, and the heap always expands the node with the smallest tentative distance, guaranteeing optimality for non‑negative weights.
Q2Can you compute the minimum number of edges between every pair of nodes efficiently? Which algorithm would you use?
Yes, by running BFS from each node (O(V*(V+E))) or, for dense graphs, using the Floyd‑Warshall algorithm (O(V^3)) to compute all‑pairs shortest paths in an unweighted graph.
Q3In a massive graph that cannot fit in memory, how would you still answer shortest‑path queries between two nodes?
Use external‑memory BFS or a bidirectional BFS that expands from both source and target simultaneously, drastically reducing the explored frontier. Additionally, graph partitioning or hierarchical indexing (e.g., landmarks, hub labeling) can pre‑process the graph to answer queries with sublinear I/O.
Examples
Input
[4, [[0,1],[1,2],[2,3]]], 0, 3
Output
2
Explanation: Step-by-step: with input [4, [[0,1],[1,2],[2,3]]], 0, 3, we start at node 0, traverse to node 1, then node 2, and finally node 3, giving a minimum path distance of 2
Input
[5, [[0,1],[1,2],[2,3],[3,4]]], 0, 4
Output
4
Explanation: Step-by-step: with input [5, [[0,1],[1,2],[2,3],[3,4]]], 0, 4, we start at node 0, traverse to node 1, then node 2, then node 3, and finally node 4, giving a minimum path distance of 4
Constraints
- 2 <= n <= 10^4
- 0 <= edges.length <= 2 * 10^4
- 0 <= start, target < n
- start != target
Optimal Approach & Strategy
Run a BFS from the start node, marking visited nodes and counting levels; return the level count when the target is first dequeued, otherwise return -1 if the queue empties.
Brute Force Approach
Enumerate every possible path from start to target using recursion or backtracking, tracking the shortest length found; this quickly explodes to exponential time on larger graphs.
Verified Code Solutions
function solution(n, edges, start, target) {
if (start < 0 || start >= n || target < 0 || target >= n) {
return -1;
}
let graph = new Array(n).fill(0).map(() => []);
for (let edge of edges) {
graph[edge[0]].push(edge[1]);
graph[edge[1]].push(edge[0]);
}
let queue = [[start, 0]];
let visited = new Set([start]);
while (queue.length > 0) {
let [node, distance] = queue.shift();
if (node === target) {
return distance;
}
for (let neighbor of graph[node]) {
if (!visited.has(neighbor)) {
queue.push([neighbor, distance + 1]);
visited.add(neighbor);
}
}
}
return -1;
}class Solution {
public:
int solution(int n, vector<vector<int>>& edges, int start, int target) {
if (start < 0 || start >= n || target < 0 || target >= n) {
return -1;
}
vector<vector<int>> graph(n);
for (auto& edge : edges) {
graph[edge[0]].push_back(edge[1]);
graph[edge[1]].push_back(edge[0]);
}
queue<pair<int, int>> q;
q.push({start, 0});
unordered_set<int> visited;
visited.insert(start);
while (!q.empty()) {
auto node = q.front();
q.pop();
if (node.first == target) {
return node.second;
}
for (int neighbor : graph[node.first]) {
if (visited.find(neighbor) == visited.end()) {
q.push({neighbor, node.second + 1});
visited.insert(neighbor);
}
}
}
return -1;
}
};import java.util.*;
class Solution {
public int solution(int n, int[][] edges, int start, int target) {
if (start < 0 || start >= n || target < 0 || target >= n) {
return -1;
}
List<List<Integer>> graph = new ArrayList<>();
for (int i = 0; i < n; i++) {
graph.add(new ArrayList<>());
}
for (int[] edge : edges) {
graph.get(edge[0]).add(edge[1]);
graph.get(edge[1]).add(edge[0]);
}
Queue<int[]> queue = new LinkedList<>();
queue.offer(new int[] {start, 0});
Set<Integer> visited = new HashSet<>();
visited.add(start);
while (!queue.isEmpty()) {
int[] node = queue.poll();
if (node[0] == target) {
return node[1];
}
for (int neighbor : graph.get(node[0])) {
if (!visited.contains(neighbor)) {
queue.offer(new int[] {neighbor, node[1] + 1});
visited.add(neighbor);
}
}
}
return -1;
}
}from collections import deque
def solution(n, edges, start, target):
if start < 0 or start >= n or target < 0 or target >= n:
return -1
graph = [[] for _ in range(n)]
for u, v in edges:
graph[u].append(v)
graph[v].append(u)
queue = deque([(start, 0)])
visited = {start}
while queue:
node, distance = queue.popleft()
if node == target:
return distance
for neighbor in graph[node]:
if neighbor not in visited:
queue.append((neighbor, distance + 1))
visited.add(neighbor)
return -1function solution(n, edges, start, target) {
if (start < 0 || start >= n || target < 0 || target >= n) {
return -1;
}
let graph = new Array(n).fill(0).map(() => []);
for (let edge of edges) {
graph[edge[0]].push(edge[1]);
graph[edge[1]].push(edge[0]);
}
let queue = [[start, 0]];
let visited = new Set([start]);
while (queue.length > 0) {
let [node, distance] = queue.shift();
if (node === target) {
return distance;
}
for (let neighbor of graph[node]) {
if (!visited.has(neighbor)) {
queue.push([neighbor, distance + 1]);
visited.add(neighbor);
}
}
}
return -1;
}Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.