Practice › Graphs
Shortest Path in an Unweighted Graph
Medium · Graphs · Asked at Amazon, Google, Microsoft, Uber
Find the minimum number of edges on a path from node 1 to node n, or -1 if node n is unreachable.
Input
First line: n m. Next m lines: u v — an undirected edge (nodes are 1..n).
Output
The shortest distance, or -1.
Constraints
- 2 ≤ n ≤ 10^5
- 0 ≤ m ≤ 2·10^5
BFS finds shortest paths when every edge has the same weight.
Example 1
Input
4 4 1 2 2 3 3 4 1 3
Output
2
Example 2
Input
3 1 1 2
Output
-1
Hints
- When every edge has the same length, BFS reaches nodes in order of their distance.
- Store dist[] (−1 = unvisited). The first time BFS reaches a node is its shortest distance.
Approach
BFS from node 1 with dist[1] = 0. When a node u is popped, every unvisited neighbour v gets dist[v] = dist[u] + 1 and is pushed. BFS processes nodes in non-decreasing distance order, so the first assignment is already the shortest. Print dist[n], which stays -1 if n was never reached. DFS does not give shortest paths.
Complexity: O(n + m) time · O(n + m) space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<vector<int>> adj(n + 1);
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
vector<int> dist(n + 1, -1);
queue<int> q;
dist[1] = 0;
q.push(1);
while (!q.empty()) {
int u = q.front();
q.pop();
for (int v : adj[u])
if (dist[v] == -1) {
dist[v] = dist[u] + 1;
q.push(v);
}
}
cout << dist[n] << "\n";
return 0;
}Python solution
import sys
from collections import deque
data = list(map(int, sys.stdin.read().split()))
n, m = data[0], data[1]
adj = [[] for _ in range(n + 1)]
for i in range(m):
u, v = data[2 + 2 * i], data[3 + 2 * i]
adj[u].append(v)
adj[v].append(u)
dist = [-1] * (n + 1)
dist[1] = 0
q = deque([1])
while q:
u = q.popleft()
for v in adj[u]:
if dist[v] == -1:
dist[v] = dist[u] + 1
q.append(v)
print(dist[n])Java solution
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(), m = sc.nextInt();
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i <= n; i++) adj.add(new ArrayList<>());
for (int i = 0; i < m; i++) {
int u = sc.nextInt(), v = sc.nextInt();
adj.get(u).add(v);
adj.get(v).add(u);
}
int[] dist = new int[n + 1];
Arrays.fill(dist, -1);
dist[1] = 0;
ArrayDeque<Integer> q = new ArrayDeque<>();
q.add(1);
while (!q.isEmpty()) {
int u = q.poll();
for (int v : adj.get(u))
if (dist[v] == -1) {
dist[v] = dist[u] + 1;
q.add(v);
}
}
System.out.println(dist[n]);
}
}Solve Shortest Path in an Unweighted Graph online · All practice problems