Find City with Fewest Reachable

public class Solution {
    public Integer findTheCity(Integer n, int[][] edges, Integer distanceThreshold) {
        // Your code goes here
    }
}

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.

With a threshold of 4, each city can reach different numbers of neighbors:

• City 0: reaches cities 1 (dist 3) and 2 (dist 4) → 2 reachable
• City 1: reaches cities 0 (dist 3), 2 (dist 1), 3 (dist 2) → 3 reachable
• City 2: reaches cities 0 (dist 4), 1 (dist 1), 3 (dist 1) → 3 reachable
• City 3: reaches cities 1 (dist 2) and 2 (dist 1) → 2 reachable ← tied with city 0, but highest number wins!

Cities 0 and 3 are tied with 2 reachable each. The tie-breaking rule says return the highest-numbered city, so city 3 is 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.

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.

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)

Walkthrough

Let's trace through with 4 cities, edges [[0,1,3], [1,2,1], [1,3,4], [2,3,1]], and threshold 4.

Step 1: Initialize Distance Matrix

Start with direct edge weights. Diagonal is 0, missing edges are ∞.

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][2] updates: 0→2 was ∞, but 0→1→2 = 3+1 = 4
• 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 = 4+1 = 5 (better than 7)
• dist[1][3] updates: 1→2→3 = 1+1 = 2 (better than direct 4)

Step 3: Count Reachable Cities (threshold=4)

After Floyd-Warshall completes, for each city count neighbors within threshold:

Cities 0 and 3 tie with 2 reachable each. Tie-breaking picks the highest-numbered city, so return 3.

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

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)

public int findTheCity(int n, int[][] edges, int threshold) {
    int INF = (int) 1e9;
    int[][] dist = new int[n][n];
    
    for (int i = 0; i < n; i++) {
        Arrays.fill(dist[i], INF);
        dist[i][i] = 0;
    }
    
    // Fill in direct edges (bidirectional)
    for (int[] e : edges) {
        dist[e[0]][e[1]] = Math.min(dist[e[0]][e[1]], e[2]);
        dist[e[1]][e[0]] = Math.min(dist[e[1]][e[0]], e[2]);
    }
    
    // Floyd-Warshall: try each vertex as intermediate
    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                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
    int result = 0, minReachable = n;
    
    for (int city = 0; city < n; city++) {
        int count = 0;
        for (int j = 0; j < n; j++) {
            if (city != j && dist[city][j] <= threshold) count++;
        }
        if (count <= minReachable) {
            minReachable = count;
            result = city;
        }
    }
    
    return result;
}