DSA Tracker

Visualize

Find the City with Fewest Reachable Neighbors

All-pairs shortest paths, then pick the city with the smallest reachable count

time O(n^3)space O(n^2)

The road weights only matter through the shortest total distance between every pair of cities, so the first job is an all-pairs shortest-path table — Floyd-Warshall, since n is small: let every city get one turn as an allowed waypoint, and let paths route through it if that shortens anything. Once every dist[i][j] is final, walk the cities in order and count how many others each one reaches within the threshold. Keep the smallest count seen, using <= rather than < when comparing — since ties are then overwritten by the later (larger) label automatically, no extra tie-break logic is needed.

Details

Animated on: 4 cities, weighted roads 0-1(3), 1-2(1), 1-3(4), 2-3(1), distanceThreshold = 4 — find the city that can reach the fewest other cities within that distance, preferring the larger label on a tie.

Problem:Find the City With the Smallest Number of Neighbors at a Threshold DistanceMedium

Pattern:Shortest Path

All-pairs shortest paths, then pick the city with the smallest reachable count

step 1 / 9

4 cities, roads have travel weights, threshold = 4

A city qualifies by counting how many OTHER cities it can reach within a total travel distance of 4 — not by how many roads it touches directly. City 1 for instance reaches city 3 at weight 4 only through city 2, not the direct road weighing 4. So shortest paths between every pair have to be known first.

Pseudocode
1FUNCTION findCity(n, edges, threshold):
2  dist <- n x n matrix, 0 on diagonal, INFINITY elsewhere
3  FOR EACH (u, v, w) IN edges
4    dist[u][v] <- w, dist[v][u] <- w
5  FOR k FROM 0 TO n - 1
6    dist[i][j] <- MIN(dist[i][j], dist[i][k] + dist[k][j])
7      FOR ALL i, j
8  best <- -1, bestCount <- n
9  FOR c FROM 0 TO n - 1
10    count <- COUNT j != c WHERE dist[c][j] <= threshold
11    IF count <= bestCount
12      best <- c, bestCount <- count
13  RETURN best

← / → step · space play · Home restart

Every step in words

Show all 9 steps
  1. A city qualifies by counting how many OTHER cities it can reach within a total travel distance of 4 — not by how many roads it touches directly. City 1 for instance reaches city 3 at weight 4 only through city 2, not the direct road weighing 4. So shortest paths between every pair have to be known first.
  2. Letting paths route through city 1, some pair got shorter: dist[i][j] <- MIN(dist[i][j], dist[i][1] + dist[1][j]) improved at least one entry. After all 4 cities have had this turn, every dist[i][j] is the true shortest road distance.
  3. Letting paths route through city 2, some pair got shorter: dist[i][j] <- MIN(dist[i][j], dist[i][2] + dist[2][j]) improved at least one entry. After all 4 cities have had this turn, every dist[i][j] is the true shortest road distance.
  4. Shortest distances from each city: 0 -> [0, 3, 4, 5], 1 -> [3, 0, 1, 2], 2 -> [4, 1, 0, 1], 3 -> [5, 2, 1, 0]. Now count, for each city, how many others sit within 4.
  5. City 0 reaches 2 others within 4 (1 at 3, 2 at 4). That is <= the best count so far (4), so this becomes the new answer — ties favor the larger label, and using <= instead of < is exactly what makes that happen.
  6. City 1 reaches 3 others within 4 (0 at 3, 2 at 1, 3 at 2). That is more than the best count so far (2), so city 0 stays the answer.
  7. City 2 reaches 3 others within 4 (0 at 4, 1 at 1, 3 at 1). That is more than the best count so far (2), so city 0 stays the answer.
  8. City 3 reaches 2 others within 4 (1 at 2, 2 at 1). That is <= the best count so far (2), so this becomes the new answer — ties favor the larger label, and using <= instead of < is exactly what makes that happen.
  9. Every city checked: counts were [2, 3, 3, 2]. The smallest count is 2, and city 3 is the LARGEST label among the cities tied at that count. RETURN 3.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Find the City With the Smallest Number of Neighbors at a Threshold Distance in the editorAll Graph problemsBack to roadmap