Fewest Hops From One Town to Every Other
Solve this ProblemYou are given a network of towns connected by two-way roads as an adjacency list, and a starting town. Every road counts as one hop. For every town, find the fewest hops needed to get there from the starting town, or -1 if it cannot be reached.
Because all roads cost the same, a breadth-first search discovers each town by its shortest route the first time it reaches it.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
1 ≤ n ≤ 10 towns numbered 0 … n-1; graph[u] lists, in increasing order, every town directly linked to u by a road (adjacency-list form of an undirected graph) - ◆
If v is in graph[u] then u is in graph[v]; every road counts as exactly one hop - ◆
0 ≤ src < n is the starting town - ◆
Return an array where entry i is the fewest hops from src to town i, or -1 if town i cannot be reached
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Keep Relaxing Distances Until Nothing Improves
BruteStart with distance 0 for the source and infinity for every other town. Sweep over all towns again and again: from a town with a known distance d, every neighbour can be reached in d + 1 hops, so lower the neighbour's distance if that is better. Stop when a whole sweep changes nothing (at most n sweeps), then replace remaining infinities by -1. Each sweep costs O(n + E), and up to n sweeps may be needed.
O(n · (n + E))O(n)1class Solution {
2 public int[] stepsFromSource(int[][] graph, int src) {
3 int n = graph.length;
4 int INF = Integer.MAX_VALUE;
5 int[] dist = new int[n];
6 Arrays.fill(dist, INF);
7 dist[src] = 0;
8 boolean changed = true;
9 while (changed) {
10 changed = false;
11 for (int u = 0; u < n; u++) {
12 if (dist[u] == INF) continue;
13 for (int v : graph[u]) {
14 if (dist[u] + 1 < dist[v]) {
15 dist[v] = dist[u] + 1;
16 changed = true;
17 }
18 }
19 }
20 }
21 for (int i = 0; i < n; i++) {
22 if (dist[i] == INF) dist[i] = -1;
23 }
24 return dist;
25 }
26}Optimal — Breadth-First Search From the Source
OptimalEvery road costs one hop, so a breadth-first search visits towns in order of increasing distance. Give the source distance 0 and queue it; take a town from the queue and give every neighbour that has no distance yet the town's distance + 1, then queue it. A town's distance is fixed the first time it is reached, and towns never reached keep -1. Each town and road is handled once: O(n + E).
O(n + E)O(n)1class Solution {
2 public int[] stepsFromSource(int[][] graph, int src) {
3 int n = graph.length;
4 int[] dist = new int[n];
5 Arrays.fill(dist, -1);
6 dist[src] = 0;
7 Deque<Integer> queue = new ArrayDeque<>();
8 queue.add(src);
9 while (!queue.isEmpty()) {
10 int u = queue.poll();
11 for (int v : graph[u]) {
12 if (dist[v] == -1) {
13 dist[v] = dist[u] + 1;
14 queue.add(v);
15 }
16 }
17 }
18 return dist;
19 }
20}