Fewest Hops
A network has n nodes numbered 0 to n - 1. links is a list of pairs [a, b], each a link that can be crossed in either direction. The same pair may appear more than once.
Return the smallest number of links that must be crossed to go from source to goal. Return 0 when source == goal, and -1 when goal cannot be reached from source.
Example 1
n 5
links [[0,1],[1,2],[2,3],[3,4],[0,4]]
source 0
goal 3
returns 2
Going 0 to 4 to 3 crosses 2 links; going through 1 and 2 would take 3.
Example 2
n 4
links [[0,1],[2,3]]
source 0
goal 3
returns -1
Nodes 0 and 3 are in different parts of the network.
Constraints
1 <= n <= 500 <= len(links) <= 100links[i] = [a, b]with0 <= a, b < nanda != b0 <= source, goal < n
Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.
More Graphs problems
- Follow the ArrowsEasy
- Forms a TreeEasy
- Groups After Each MergeEasy
- Largest CrowdEasy
- Loop in the WiringEasy
- Mutual FollowsEasy
- Paint BucketEasy
- Pointer Loop LengthEasy