Graphs

Find City with Fewest Reachable

medium
DESCRIPTION (inspired by Leetcode.com)

A regional planning committee wants to identify the most "isolated" city in a road network. Given n cities connected by bidirectional roads with varying distances, find the city that can reach the fewest other cities within a given distance threshold.

If multiple cities have the same minimum count, return the city with the highest number.

Note: The distance between two cities is the shortest path distance considering all possible routes.

Example 1:

012332145Threshold: 4Answer: 31 reachable

Input:

n = 4
edges = [[0,1,3], [1,2,1], [1,3,4], [2,3,1]]
distanceThreshold = 4

Output:

3

Explanation: City 3 can only reach city 1 (distance 4) within the threshold. Cities 0 and 2 can each reach 2 cities, and city 1 can reach 3 cities. City 3 has the fewest reachable.

Example 2:

01234231118Threshold: 2Answer: 01 reachable

Input:

n = 5
edges = [[0,1,2], [0,4,8], [1,2,3], [1,4,2], [2,3,1], [3,4,1]]
distanceThreshold = 2

Output:

0

Explanation: With threshold 2, city 0 can only reach city 1 (distance 2). Other cities can reach more neighbors. City 0 has the fewest reachable.

Explanation

Understanding the Problem

A regional planning committee wants to identify the most "isolated" city in a road network for building a new data center. The ideal location minimizes connectivity to reduce network congestion risks. Given a network of cities connected by bidirectional roads with travel distances, find the city that can reach the fewest other cities within a given distance threshold.
0123ANSWER32145Threshold: 4City 3 reaches onlycity 1 within dist 4→ Fewest reachable!
With a threshold of 4, each city can reach different numbers of neighbors:
  • City 0: reaches cities 1 (dist 3) and 2 (dist 2) → 2 reachable
  • City 1: reaches cities 0 (dist 3), 2 (dist 1), 3 (dist 4) → 3 reachable
  • City 2: reaches cities 0 (dist 2), 1 (dist 1) → 2 reachable
  • City 3: reaches only city 1 (dist 4) → 1 reachable ← fewest!
City 3 can reach the fewest other cities, making it the most isolated and our answer.

Why This Differs from Previous Problems

In Network Delay Time, we needed shortest paths from one source to all nodes. Dijkstra was perfect. In Cheapest Flights, we needed shortest path from one source to one destination with constraints where some modification in Dijkstra worked.
But here, we need shortest paths from every city to every other city. Running Dijkstra n times for each node will give us the result, but there's a more optimised approach: Floyd-Warshall.
Single-SourceNetwork Delay TimeCheapest FlightsDijkstra: O((V+E) log V)All-PairsFind City FewestReachableFloyd-Warshall: O(V³)

The Floyd-Warshall Approach

Floyd-Warshall finds shortest paths between all pairs of vertices using dynamic programming. The idea is that for each pair (i, j), we check if going through an intermediate vertex k gives a shorter path or not.
ijdist[i][j]kdist[i][k]dist[k][j]Relaxation:dist[i][j] = min(dist[i][j],dist[i][k] + dist[k][j])
The algorithm iterates through all possible intermediate vertices k, and for each k, checks if it provides a shorter path for every pair (i, j).

The Algorithm Step by Step

  1. Initialize: dist[i][j] = edge weight if edge exists, 0 if i=j, ∞ otherwise
  2. For each intermediate vertex k (outer loop):
    • For each source i (middle loop):
      • For each destination j (inner loop):
        • If dist[i][k] + dist[k][j] < dist[i][j], update dist[i][j]
  3. Count reachable: For each city, count how many cities are within threshold
  4. Return: City with minimum reachable count (highest numbered if tied)
The order of loops is critical in Floyd-Warshall. The intermediate vertex k must be the outermost loop. This ensures that when we consider paths through vertex k, we've already computed the best paths using vertices 0 to k-1.

Walkthrough

Let's trace through with 4 cities, edges [[0,1,3], [0,2,2], [1,2,1], [1,3,4], [2,3,5]], and threshold 4.
Step 1: Initialize Distance Matrix
Start with direct edge weights. Diagonal is 0, missing edges are ∞.
Initial dist[][] matrix:01230032∞13014221053∞450NoteRoads are bidirectionalso dist[i][j] = dist[j][i](symmetric matrix)
Step 2: Process k=0, k=1, k=2, k=3
For each intermediate vertex, check if routing through it improves any path. After processing k=1:
  • dist[0][3] updates: 0→3 was ∞, but 0→1→3 = 3+4 = 7
After processing k=2:
  • dist[0][3] updates again: 0→2→3 = 2+5 = 7 (same)
  • dist[1][3] stays 4 (1→3 direct is better than 1→2→3 = 1+5 = 6)
Step 3: Count Reachable Cities (threshold=4)
After Floyd-Warshall completes, for each city count neighbors within threshold:
Reachable count (threshold=4):0→ cities 1 (dist 3), 2 (dist 2) = 2 reachable1→ cities 0 (dist 3), 2 (dist 1), 3 (dist 4) = 3 reachable2→ cities 0 (dist 2), 1 (dist 1) = 2 reachable3→ only city 1 (dist 4) = 1 reachable ✓
City 3 has the fewest reachable cities (1), so return 3.
Tie-breaking rule: If multiple cities have the same minimum reachable count, return the city with the highest number. This is why we iterate from 0 to n-1 and update the answer whenever we find a city with count ≤ current minimum.

When to Use Floyd-Warshall vs. Running Dijkstra n Times

ScenarioFloyd-Warshalln × Dijkstra
Time complexityO(V³)O(V · (V+E) log V)
Dense graph (E ≈ V²)O(V³) ✓O(V³ log V)
Sparse graph (E ≈ V)O(V³)O(V² log V) ✓
Simple implementation✓ Three nested loopsMore complex
Works with negative edges✓ (no negative cycles)✗
For this problem, V ≤ 100, so Floyd-Warshall's O(V³) = O(10⁶) is fast enough and simpler to implement.

Solution

The solution applies Floyd-Warshall to compute all-pairs shortest paths, then counts reachable cities for each city:
  1. Initialize distance matrix from edges (bidirectional, so set both directions)
  2. Run Floyd-Warshall to find all shortest paths
  3. Count reachable cities within threshold for each city
  4. Return city with minimum count (highest number if tied)
|
[[u, v, weight], ...]
|
cities
|
max distance
Try these examples:
Visualization
def find_the_city(n, edges, distance_threshold):
    # Initialize distance matrix with infinity
    dist = [[float('inf')] * n for _ in range(n)]
    for i in range(n):
        dist[i][i] = 0
    
    # Fill in direct edges (bidirectional)
    for u, v, w in edges:
        dist[u][v] = w
        dist[v][u] = w
    
    # Floyd-Warshall: try each vertex as intermediate
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
    
    # Find city with fewest reachable within threshold
    result = 0
    min_reachable = n
    
    for city in range(n):
        count = sum(1 for j in range(n) 
                    if city != j and dist[city][j] <= threshold)
        if count <= min_reachable:
            min_reachable = count
            result = city
    
    return result
31410123012300∞∞∞1∞0∞∞2∞∞0∞3∞∞∞0

Initialize distance matrix: diagonal = 0, all others = ∞

0 / 21

Floyd-Warshall finding all-pairs shortest paths
What is the time complexity of this solution?
1

O(m * n * 4^L)

2

O(V³)

3

O(m * n)

4

O(4^L)

Mark as read

Next: Dynamic Programming Fundamentals

© 2026 Optick Labs Inc. All rights reserved.