Shortest Path in Unweighted Graph

Given an unweighted graph, return the minimum number of edges needed to travel from source to target. Pattern focus: Unweighted BFS distance. Since all edges have the same cost, BFS naturally gives the shortest distance.

Input Format

n = node count, edges = unweighted undirected edges, source = start node, target = destination node

Output Format

minimum number of edges from source to target, or -1

Constraints

  • 1 <= n <= 10^5
  • 1 <= edges.length <= 2 * 10^5

Examples

Example 1:

Input:

n = 5
edges = [[0,1],[1,2],[2,3],[1,4]]
source = 0
target = 3

Output:

3

Explanation:

The shortest route is 0 -> 1 -> 2 -> 3.

Example 2:

Input:

n = 4
edges = [[0,1],[1,2]]
source = 0
target = 3

Output:

-1

Explanation:

Node 3 is disconnected.

Example 3:

Input:

n = 2
edges = [[0,1]]
source = 0
target = 1

Output:

1

Explanation:

A single edge is one step.

Loading...
Shortest Path in Unweighted Graph