Find the City With Fewest Neighbours Within Threshold Distance

Problem Statement❯

Given n cities numbered from 0 to n - 1, and an array edges where edges[i] = [from_i, to_i, weight_i] represents a bidirectional road between cities from_i and to_i with travel distance weight_i, you are also given a distance threshold distanceThreshold.

Your task is to find the city with the smallest number of other cities that can be reached from it through any path such that the total distance is less than or equal to distanceThreshold.

If there are multiple cities with the same minimal number of reachable neighbours, return the city with the greatest number.

Examples❯

n	Edges	Threshold	Output	Description
4	[[0,1,3],[1,2,1],[1,3,4],[2,3,1]]	4	3	City 3 can reach only city 2 within threshold 4
5	[[0,1,2],[0,4,8],[1,2,3],[1,4,2],[2,3,1],[3,4,1]]	2	0	City 0 can reach only city 1 within threshold 2
2	[[0,1,10]]	5	1	No city can reach the other, return the city with the greatest index

Solution❯

To solve this problem, we need to calculate the shortest distances between all pairs of cities and count how many cities each city can reach within the given distanceThreshold.

Two main algorithms can be used for shortest path calculation:

Floyd-Warshall Algorithm: Suitable when n is small (typically n ≤ 100). It computes all-pairs shortest paths using dynamic programming.
Dijkstra’s Algorithm: Can be applied individually for each city using a min-heap to optimize time for sparse graphs.

After computing shortest paths:

For each city, count the number of cities reachable within distanceThreshold.
Track the city with the minimum count of reachable cities. If multiple cities have the same count, pick the one with the highest index.

Algorithm Steps❯

Initialize a 2D matrix dist with infinity, except dist[i][i] = 0.
Fill in direct distances from the edges input.
Run the Floyd-Warshall algorithm:
1. For each intermediate node k, update dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]).
For each city, count the number of other cities it can reach with distance ≤ threshold.
Return the city with the fewest reachable cities (use max index in case of tie).

Code

JavaScript

function findTheCity(n, edges, distanceThreshold) {
  const INF = 1e9;
  const dist = Array.from({ length: n }, () => Array(n).fill(INF));

  for (let i = 0; i < n; i++) dist[i][i] = 0;
  for (const [u, v, w] of edges) {
    dist[u][v] = w;
    dist[v][u] = w;
  }

  for (let k = 0; k < n; k++) {
    for (let i = 0; i < n; i++) {
      for (let j = 0; j < n; j++) {
        if (dist[i][k] + dist[k][j] < dist[i][j]) {
          dist[i][j] = dist[i][k] + dist[k][j];
        }
      }
    }
  }

  let answer = -1;
  let minReachable = n;

  for (let i = 0; i < n; i++) {
    let count = 0;
    for (let j = 0; j < n; j++) {
      if (i !== j && dist[i][j] <= distanceThreshold) count++;
    }
    if (count <= minReachable) {
      minReachable = count;
      answer = i;
    }
  }

  return answer;
}

console.log(findTheCity(4, [[0,1,3],[1,2,1],[1,3,4],[2,3,1]], 4)); // Output: 3
console.log(findTheCity(5, [[0,1,2],[0,4,8],[1,2,3],[1,4,2],[2,3,1],[3,4,1]], 2)); // Output: 0

⬅ Previous TopicFloyd Warshall Algorithm for All-Pairs Shortest Path

Next Topic ⮕Minimum Spanning Tree in Graphs