Find the City With Fewest Neighbours Within Threshold Distance - Visualization

Graphs

Contents

ProblemExamplesSolutionAlgorithmCode

Problem Statement❯

Given n cities numbered from 0 to n - 1, and an array edges where edges[i] = [fromi, toi, weighti] represents a bidirectional road between cities fromi and toi with travel distance weighti, 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❯

Understanding the Problem

We are given n cities, numbered from 0 to n - 1, and a list of edges that represent bidirectional roads between cities. Each edge contains a source city, a destination city, and the distance between them. We are also given a distanceThreshold, which defines the maximum distance we can travel from any city.

Our goal is to find the city with the fewest number of reachable cities within this threshold. If there are multiple cities with the same minimum count, we return the city with the largest index.

Step-by-Step Solution with Example

Step 1: Understand the Input

Suppose we have n = 4 cities, the following edges: 

[
  [0, 1, 3],
  [1, 2, 1],
  [2, 3, 4],
  [0, 3, 7]
]
And a distanceThreshold = 4.

Step 2: Represent the Graph

We create an adjacency matrix to represent the shortest distance between all pairs of cities. Initially, set the distance between each pair as Infinity, and set dist[i][i] = 0. Then fill in the given edges.

Step 3: Use Floyd-Warshall to Compute All-Pairs Shortest Paths

Floyd-Warshall is ideal when n is small (like ≤ 100). It updates the shortest distance between every pair of cities using a dynamic programming approach. For each intermediate city k, update: 


if (dist[i][j] > dist[i][k] + dist[k][j]) {
    dist[i][j] = dist[i][k] + dist[k][j];
}

Step 4: Count Reachable Cities

For each city, count how many other cities are reachable such that dist[i][j] ≤ distanceThreshold. Do not count the city itself.

Step 5: Track the Best Candidate

As we compute the reachable count for each city, track the city with the fewest reachable cities. If there's a tie, choose the city with the higher index.

Step 6: Final Output

From our example, city 3 can reach only one city within distance 4, so it will be the answer.

Edge Cases

  • No reachable neighbors: A city completely disconnected from others within the threshold will have a count of 0.
  • Multiple cities with same count: We must return the one with the highest index.
  • Disconnected components: Floyd-Warshall handles this by keeping unreachable distances as Infinity.
  • Zero threshold: Only self-reachability is allowed, so all cities will have 0 reachable neighbors.

Finally

This problem is a great use case for the Floyd-Warshall algorithm, which efficiently handles all-pairs shortest paths for small graphs. By applying it, we can easily evaluate reachability for every city and determine the one that meets the problem's criteria. Always keep in mind the edge conditions, such as tie-breaking and unreachable nodes, to ensure a complete and accurate solution.

Algorithm Steps❯

  1. Initialize a 2D matrix dist with infinity, except dist[i][i] = 0.
  2. Fill in direct distances from the edges input.
  3. 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]).
  4. For each city, count the number of other cities it can reach with distance ≤ threshold.
  5. Return the city with the fewest reachable cities (use max index in case of tie).

Code

C
C++
Python
Java
JS
Go
Rust
Kotlin
Swift
TS
#include <stdio.h>
#define INF 1000000

void floydWarshall(int n, int dist[n][n]) {
    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];
}

int findTheCity(int n, int edges[][3], int edgesSize, int distanceThreshold) {
    int dist[n][n];

    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            dist[i][j] = (i == j) ? 0 : INF;

    for (int i = 0; i < edgesSize; i++) {
        int u = edges[i][0], v = edges[i][1], w = edges[i][2];
        dist[u][v] = w;
        dist[v][u] = w;
    }

    floydWarshall(n, dist);

    int result = -1, minReachable = n;
    for (int i = 0; i < n; i++) {
        int count = 0;
        for (int j = 0; j < n; j++)
            if (i != j && dist[i][j] <= distanceThreshold)
                count++;
        if (count <= minReachable) {
            minReachable = count;
            result = i;
        }
    }
    return result;
}

int main() {
    int edges1[][3] = {{0,1,3},{1,2,1},{1,3,4},{2,3,1}};
    int result1 = findTheCity(4, edges1, 4, 4);
    printf("%d\n", result1); // Output: 3

    int edges2[][3] = {{0,1,2},{0,4,8},{1,2,3},{1,4,2},{2,3,1},{3,4,1}};
    int result2 = findTheCity(5, edges2, 6, 2);
    printf("%d\n", result2); // Output: 0

    return 0;
}

Comments

💬 Please keep your comment relevant and respectful. Avoid spamming, offensive language, or posting promotional/backlink content.
All comments are subject to moderation before being published.

Loading comments...