Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

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

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

  1. When every edge has the same length, BFS reaches nodes in order of their distance.
  2. 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