☕ DSA Java Articles

Topics › Graphs › Shortest Path Algorithms and Problems

Find the city with the smallest number of neighbors

Hard TUF ID 521 A2Z

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

There are n cities numbered 0 to n - 1 and a list of two-way roads [from, to, weight]. Given an integer distanceThreshold, a city “can reach” another city if the shortest path between them has total weight at most the threshold. Return the city that can reach the fewest other cities. If several cities tie, return the one with the largest number.

Constraints (LeetCode 1334): 2 ≤ n ≤ 100, 1 ≤ weight, distanceThreshold ≤ 10^4, all pairs (from, to) distinct.

Example 1

n = 4, edges = [[0,1,3], [1,2,1], [1,3,4], [2,3,1]], distanceThreshold = 4
answer = 3
// reachable within 4:  city 0 -> {1, 2}      city 1 -> {0, 2, 3}
//                      city 2 -> {0, 1, 3}   city 3 -> {1, 2}
// cities 0 and 3 both reach 2 others; the larger number, 3, wins

Example 2

n = 5, edges = [[0,1,2], [0,4,8], [1,2,3], [1,4,2], [2,3,1], [3,4,1]], distanceThreshold = 2
answer = 0          // city 0 reaches only city 1 within distance 2

“Reach” is about the shortest path, not single roads. In Example 1 the direct road 1 - 3 has weight 4, but 1 → 2 → 3 costs only 2. So the task is: compute the shortest distance between every pair of cities, count for each city how many others lie within the threshold, and pick the minimum with the tie rule. The two approaches differ only in how they get the all-pairs distances.

Approach 1: Floyd-Warshall

Intuition. We need distances between all pairs, and n ≤ 100, so the classic all-pairs algorithm fits naturally. Floyd-Warshall starts from the direct road weights and, for each vertex via in turn, allows paths to pass through via: dist[i][j] = min(dist[i][j], dist[i][via] + dist[via][j]). After every vertex has been allowed as an intermediate, dist[i][j] is the true shortest distance. Roads are two-way, so both dist[u][v] and dist[v][u] start at the road weight.

Choosing INF = Integer.MAX_VALUE / 2 means INF + INF still fits in an int, so the inner loop needs no “is it finite?” checks. An unreachable pair stays at or above INF, far above any threshold.

The tie rule is handled in the final scan. Visit cities in increasing order and replace the current answer whenever a city’s count is less than or equal to the best so far. A later city with the same count then overwrites an earlier one, so the largest number wins.

Algorithm.

  1. Fill dist with INF, set dist[i][i] = 0, and set both directions of every road.
  2. Run the triple loop with via outermost.
  3. For each city, count j != city with dist[city][j] ≤ threshold.
  4. Keep the city with the smallest count, preferring the later city on ties.
static int floydWarshall(int n, int[][] edges, int distanceThreshold) {
    int[][] dist = new int[n][n];
    for (int[] row : dist) Arrays.fill(row, INF);
    for (int i = 0; i < n; i++) dist[i][i] = 0;
    for (int[] e : edges) {                          // roads are two-way
        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]);
    }
    for (int via = 0; via < n; via++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (dist[i][via] + dist[via][j] < dist[i][j]) dist[i][j] = dist[i][via] + dist[via][j];
            }
        }
    }
    int answer = -1, fewest = Integer.MAX_VALUE;
    for (int city = 0; city < n; city++) {
        int reachable = 0;
        for (int j = 0; j < n; j++) if (j != city && dist[city][j] <= distanceThreshold) reachable++;
        if (reachable <= fewest) {                   // "<=" lets a later (larger) city win ties
            fewest = reachable;
            answer = city;
        }
    }
    return answer;
}

Complexity. Time O(n³) for the triple loop, plus O(n²) for counting. Space O(n²) for the matrix. For n = 100 that is a million simple steps.

Dry run on Example 1, distances after Floyd-Warshall:

from \ to 0 1 2 3 within 4
0 0 3 4 5 2
1 3 0 1 2 3
2 4 1 0 1 3
3 5 2 1 0 2

The scan sets the answer to city 0 (count 2), keeps it for cities 1 and 2 (count 3), and replaces it with city 3 (count 2, a tie). The answer is 3.

Approach 2: Dijkstra from every city

Intuition. All weights are positive, so Dijkstra gives the shortest distances from one city in O(E log E). Running it from each city gives all pairs in O(n · E log E), which beats O(n³) when the graph is sparse. A further saving comes from the threshold. Dijkstra pops cities in increasing order of distance, so once a popped distance exceeds the threshold, every city still in the heap is even farther away and can be ignored. We can count reachable cities as they are popped and stop early.

Algorithm.

  1. Build an adjacency list with both directions of every road.
  2. For each city, run Dijkstra. Every non-stale pop with distance at most the threshold, other than the source itself, adds one to the count. Stop at the first pop beyond the threshold.
  3. Apply the same “smallest count, larger index on ties” scan.
static int dijkstraFromEach(int n, int[][] edges, int distanceThreshold) {
    List<List<int[]>> adj = new ArrayList<>();
    for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
    for (int[] e : edges) {
        adj.get(e[0]).add(new int[]{e[1], e[2]});
        adj.get(e[1]).add(new int[]{e[0], e[2]});
    }
    int answer = -1, fewest = Integer.MAX_VALUE;
    for (int city = 0; city < n; city++) {
        int reachable = countWithin(adj, city, distanceThreshold);
        if (reachable <= fewest) {
            fewest = reachable;
            answer = city;
        }
    }
    return answer;
}

static int countWithin(List<List<int[]>> adj, int src, int limit) {
    int[] dist = new int[adj.size()];
    Arrays.fill(dist, INF);
    dist[src] = 0;
    PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));
    pq.offer(new int[]{0, src});                     // {distance, city}
    int count = 0;
    while (!pq.isEmpty()) {
        int[] cur = pq.poll();
        int d = cur[0], u = cur[1];
        if (d > dist[u]) continue;                   // stale entry
        if (d > limit) break;                        // everything left in the heap is even farther
        if (u != src) count++;
        for (int[] e : adj.get(u)) {
            if (d + e[1] < dist[e[0]]) {
                dist[e[0]] = d + e[1];
                pq.offer(new int[]{dist[e[0]], e[0]});
            }
        }
    }
    return count;
}

Complexity. Time O(n · E log E) in the worst case, often much less because each search stops at the threshold. Space O(n + E) for the adjacency list and one heap at a time. With E close to n² (a dense graph) this becomes O(n³ log n), so Floyd-Warshall is the simpler choice at these sizes. For a large sparse road network, the Dijkstra version scales much better.

Choosing between the two

Floyd-Warshall is about ten lines, has no data structures, and is hard to get wrong. That makes it the right default when n is in the low hundreds. Dijkstra-from-every-city has more moving parts, but its cost depends on the number of roads rather than n³, and the threshold cut-off can make each search tiny. Both produce the same distances, so the counting and tie-break logic is shared. The Java tests check both against the same expected answers and against each other on 300 seeded random graphs.

Edge cases and pitfalls