G-43. Find the City With the Smallest Number of Neighbors at a Threshold Distance

Find the city that can reach the minimum number of other cities within a specified maximum distance threshold, using the Floyd-Warshall Algorithm for all-pairs shortest paths.

1. Problem Statement & Core Objective

We are given:

• $n$ cities, numbered from $0$ to $n-1$.
• An array of edges, where each edge connects a from city to a to city with a given weight (undirected graph).
• An integer distance threshold (distanceThreshold).

The Objective

Find the city from which we can reach the smallest number of other cities such that the shortest path distance to each of those cities is at most the distanceThreshold.

The Tie-Breaker Rule

If there are multiple cities that share the exact same minimum number of reachable neighbor cities under the threshold, choose and return the city with the greatest index number (e.g., if both city 0 and city 3 have 2 reachable neighbors, return 3).

2. Real-Life Mental Model & Analogy

Real-Life Analogy: Imagine you are planning regional logistics hubs across $n$ towns connected by roads with varying lengths. You want to pick a headquarters town that has the fewest direct or indirect delivery routes to other towns within a strict fuel-consumption limit (distanceThreshold). If two different towns tie for having the fewest reachable neighbors within that fuel limit, company policy dictates that you choose the town with the higher numerical ID for administrative convenience.

3. Prerequisite: The Floyd-Warshall Algorithm

Before solving this problem, we must know how to find the shortest paths between all pairs of vertices in a graph.

• Dijkstra's Algorithm finds shortest paths from a single source to all other nodes. We could run Dijkstra $n$ times (once from each city), but an alternative or standard approach taught for this specific pattern is Floyd-Warshall.
• Floyd-Warshall populates an $n \times n$ 2D matrix where distance[i][j] represents the shortest path from city i to city j.
• Time Complexity of Floyd-Warshall: $O(n^3)$, which is completely optimal and acceptable given typical constraints where $n$ is relatively small (e.g., $n \le 100$).

4. Step-by-Step Problem Walkthrough

Let's trace an undirected graph with $4$ cities ($0, 1, 2, 3$) and a distanceThreshold of $4$.

Step A: Building the Distance Matrix

After running Floyd-Warshall, we obtain a fully populated 2D shortest-distance matrix:

Step B: Evaluating Reachability per City (Threshold = 4)

Let's count how many cities each node can reach with a distance $\le 4$ (including itself, since distance from a city to itself is $0$):

1. City 0:

   • Reachable: City 0 (dist 0), City 1 (dist 3), City 2 (dist 4). City 3 takes dist 5 (exceeds threshold).
   • Total Count = 3 cities

2. City 1:

   • Reachable: City 0 (dist 3), City 1 (dist 0), City 2 (dist 1), City 3 (dist 2). All are $\le 4$.
   • Total Count = 4 cities

3. City 2:

   • Reachable: City 0 (dist 4), City 1 (dist 1), City 2 (dist 0), City 3 (dist 3). All are $\le 4$.
   • Total Count = 4 cities

4. City 3:

   • Reachable: City 0 (dist 5 - NO), City 1 (dist 2), City 2 (dist 3), City 3 (dist 0).
   • Total Count = 3 cities (Cities 1, 2, 3)

Step C: Applying Selection & Tie-Breaking Rules

• Minimum reachable count found: 3 cities (achieved by City 0 and City 3).
• Because there is a tie between 0 and 3, the tie-breaker dictates we pick the greatest city index.
• Result: Return 3.

5. Algorithm Design & Implementation

Here is the complete Java implementation utilizing the Floyd-Warshall algorithm pattern:

class Solution {
    public int findTheCity(int n, int[][] edges, int distanceThreshold) {
        // Step 1: Initialize the distance matrix with a large number (infinity)
        int[][] dist = new int[n][n];
        int maxVal = (int) (1e9);
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i == j) dist[i][j] = 0;
                else dist[i][j] = maxVal;
            }
        }
        
        // Step 2: Populate the distance matrix with given edge weights (undirected graph)
        for (int i = 0; i < edges.length; i++) {
            int u = edges[i][0];
            int v = edges[i][1];
            int wt = edges[i][2];
            dist[u][v] = wt;
            dist[v][u] = wt;
        }
        
        // Step 3: Run Floyd-Warshall Algorithm (All-Pairs Shortest Path)
        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    // Optimization: skip if intermediate paths are unreachable
                    if (dist[i][k] == maxVal || dist[k][j] == maxVal) {
                        continue;
                    }
                    dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
                }
            }
        }
        
        // Step 4: Evaluate each city's reachable neighbor count within threshold
        int minCount = n;
        int cityWithMinNeighbors = -1;
        
        for (int city = 0; city < n; city++) {
            int currentReachableCount = 0;
            
            for (int adjCity = 0; adjCity < n; adjCity++) {
                if (dist[city][adjCity] <= distanceThreshold) {
                    currentReachableCount++;
                }
            }
            
            // We use '<=' for the tie-breaker: if counts are equal, 
            // we update to the larger city index.
            if (currentReachableCount <= minCount) {
                minCount = currentReachableCount;
                cityWithMinNeighbors = city;
            }
        }
        
        return cityWithMinNeighbors;
    }
}

6. Flow Walkthrough of Code Execution

7. Complexity Analysis

• Time Complexity:
  • Floyd-Warshall execution: $O(n^3)$ due to the three nested loops (k, i, j).
  • City evaluation phase: $O(n^2)$ to check all pairs against the threshold.
  • Total Time Complexity: $\mathcal{O}(n^3)$, which is extremely efficient for typical constraints ($n \le 100$).
• Space Complexity: $\mathcal{O}(n^2)$ to store the $n \times n$ distance matrix.

8. Summary and Key Takeaways

• Problem Classification: This is a classic All-Pairs Shortest Path problem solved efficiently using the Floyd-Warshall Algorithm.
• Graph Representation: Because edges are bidirectional, ensure weights are populated symmetrically (dist[u][v] = wt and dist[v][u] = wt).
• Self-Loops: Distance from a city to itself is always initialized to 0, meaning every city can always reach at least itself (count starts at $\ge 1$).
• Tie-Breaking Logic: When checking neighbor counts, using currentReachableCount <= minCount ensures that if a later city has an equal number of reachable neighbors, it overwrites the previous answer, satisfying the requirement to choose the greatest city index.
• Alternative Approach: As an exercise, this problem can also be solved by running Dijkstra's Algorithm $n$ times ($O(n \cdot (V \log V + E)$), which is faster on sparse graphs.