Shortest Path in an Unweighted Graph
Problem statement
You are given an undirected graph with n nodes, numbered 0 to n - 1. Each edges[i] = [a, b] is a road between nodes a and b that you can travel in both directions. Every road has the same length.
Return the smallest number of roads on a path from source to target. If source and target are the same node, return 0. If no path connects them, return -1.
Function
shortestPath(n: int, edges: int[][], source: int, target: int) → intExamples
Example 1
n = 6edges = [[0,1],[1,2],[2,3],[3,4],[0,5],[5,4]]source = 0target = 4return = 2There are two ways from node 0 to node 4. The path 0 → 1 → 2 → 3 → 4 uses 4 roads. The path 0 → 5 → 4 uses only 2 roads, so the answer is 2.
Example 2
n = 5edges = [[0,1],[1,2],[3,4]]source = 0target = 4return = -1From node 0 you can reach only nodes 1 and 2. Node 4 is joined only to node 3, so no path reaches it and the answer is -1.
Example 3
n = 4edges = [[1,0],[2,1],[3,2]]source = 0target = 3return = 3Each road is listed with the larger node first, but roads work in both directions. The path 0 → 1 → 2 → 3 uses 3 roads, so the answer is 3.
Constraints
1 <= n <= 50000 <= edges.length <= 10^4edges[i].length == 20 <= edges[i][0], edges[i][1] < nedges[i][0] != edges[i][1]- No two edges connect the same pair of nodes.
0 <= source, target < n