Find the City With the Smallest Number of Neighbors: Floyd-Warshall
Solve Find the City With the Smallest Number of Neighbors at a Threshold Distance using Floyd-Warshall — all-pairs shortest paths, code, and a full walkthrough.
This article has an interactive companion
Don't just read it — step through it interactively, one state change at a time.
Most graph problems hand you one source and ask for the shortest path out of it. This one flips that: you need the shortest path between every pair of cities at once, then a small counting step on top. The moment you recognize "all-pairs shortest paths," a 50-line Dijkstra-per-node draft collapses into a five-line triple loop — Floyd-Warshall.
The trick isn't the counting. It's noticing that a dense, small graph is the exact setting where the simplest all-pairs algorithm wins outright. Constraints cap n at 100, so an O(n³) matrix pass is roughly a million operations — trivial — and the code is short enough to write correctly under interview pressure.
The problem
You have n cities numbered 0 to n-1 and a list of bidirectional weighted edges where edges[i] = [from, to, weight]. Given an integer distanceThreshold, count for each city how many other cities it can reach with a total path distance at most the threshold. Return the city with the smallest such count. If several cities tie, return the one with the greatest index.
Input: n = 4
edges = [[0,1,3],[1,2,1],[1,3,4],[2,3,1]]
distanceThreshold = 4
Output: 3
City 0 reaches {1, 2} → 2 cities
City 1 reaches {0, 2, 3} → 3 cities
City 2 reaches {0, 1, 3} → 3 cities
City 3 reaches {1, 2} → 2 cities
Cities 0 and 3 tie at 2 → return the larger index, 3.Two details steer the whole solution. Distance is the weighted sum along the shortest route, not an edge count — so 1 → 2 → 3 at cost 1 + 1 = 2 beats the direct 1 → 3 edge of weight 4. And the tie-break asks for the largest index, which shapes one comparison operator at the very end.
The brute force baseline
The direct reading is "shortest paths from a source," so run a single-source search from every city. With an array-scan Dijkstra that's O(n²) per source:
function findTheCity(n, edges, distanceThreshold) {
const adj = Array.from({ length: n }, () => []);
for (const [u, v, w] of edges) {
adj[u].push([v, w]);
adj[v].push([u, w]);
}
function reachableFrom(src) {
const dist = new Array(n).fill(Infinity);
dist[src] = 0;
const done = new Array(n).fill(false);
for (let step = 0; step < n; step++) {
let u = -1;
for (let i = 0; i < n; i++) // pick nearest unfinished node
if (!done[i] && (u === -1 || dist[i] < dist[u])) u = i;
if (u === -1 || dist[u] === Infinity) break;
done[u] = true;
for (const [v, w] of adj[u])
if (dist[u] + w < dist[v]) dist[v] = dist[u] + w;
}
return dist.filter((d, i) => i !== src && d <= distanceThreshold).length;
}
let best = -1, minCount = Infinity;
for (let i = 0; i < n; i++) {
const c = reachableFrom(i);
if (c <= minCount) { minCount = c; best = i; }
}
return best;
}This is correct and it's O(n³) too. But it's fiddly: you re-implement the nearest-node scan, the done array, and the reset for each of n sources. Under interview time that's a lot of surface area for an off-by-one. Floyd-Warshall computes the same all-pairs table with none of that machinery.
The key insight: all-pairs shortest paths by intermediate vertex
Reframe the question. Instead of "shortest path from source s," ask a dynamic-programming question: what is the shortest path from i to j if you're only allowed to pass through cities 0..k as intermediate stops?
Start with k = -1 (no intermediates allowed) — that's just the direct edge weights. Now let city k join the pool of allowed waypoints. For every pair (i, j), the best route either ignores k (unchanged) or detours through it:
dist[i][j] = min( dist[i][j], dist[i][k] + dist[k][j] )Sweep k from 0 to n-1, and after the last sweep dist[i][j] is the true shortest path using any intermediates. That's Floyd-Warshall. Correctness rests on the triangle inequality: if a shorter route through k exists, this relaxation finds it the moment k is admitted. The k loop must be outermost — it's the DP dimension being unlocked.
Once the matrix is filled, the original problem is a one-line scan per row.
The optimal solution
This mirrors the CODE_LINES the visualizer steps through:
function findTheCity(n, edges, distanceThreshold) {
// Distance matrix: Infinity everywhere, 0 on the diagonal
const dist = Array.from({ length: n }, () => new Array(n).fill(Infinity));
for (let i = 0; i < n; i++) dist[i][i] = 0;
// Seed the direct edge weights (undirected → both directions)
for (const [u, v, w] of edges) {
dist[u][v] = dist[v][u] = w;
}
// Floyd-Warshall: unlock each city k as an intermediate, in order
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];
}
}
}
}
// Count reachable neighbors per city, pick the min (tie → larger index)
let minReachable = n, resultCity = -1;
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;
resultCity = i; // <= (not <) so a later index wins ties
}
}
return resultCity;
}Two lines carry the subtle logic. dist[u][v] = dist[v][u] = w seeds both directions because the graph is undirected. And count <= minReachable (not <) is the tie-break: when a later city matches the current minimum, it overwrites resultCity, so the largest index always wins. Flip it to < and you'd return the smallest index instead — the wrong answer.
One caution on the addition: dist[i][k] + dist[k][j] can be Infinity + Infinity. In JavaScript that stays Infinity and the < check safely fails, so no bogus relaxation slips through. In languages with fixed-width integers you'd guard against overflow before adding.
Walkthrough
Take the example: n = 4, edges = [[0,1,3],[1,2,1],[1,3,4],[2,3,1]], threshold = 4.
After seeding edges, the matrix holds only direct connections:
to 0 to 1 to 2 to 3
fr 0 0 3 ∞ ∞
fr 1 3 0 1 4
fr 2 ∞ 1 0 1
fr 3 ∞ 4 1 0Now Floyd-Warshall sweeps k:
| k (waypoint) | relaxations that fire | effect |
|---|---|---|
| 0 | none | city 0 only touches city 1; no shortcut |
| 1 | [0][2]=4, [0][3]=7, [2][0]=4, [3][0]=7 | city 1 bridges 0 to the 2–3 side |
| 2 | [0][3]=5, [1][3]=2, [3][0]=5, [3][1]=2 | routing through 2 shortens 1→3 from 4 to 2 |
| 3 | none | no route improves by passing through 3 |
The completed all-pairs matrix:
to 0 to 1 to 2 to 3
fr 0 0 3 4 5
fr 1 3 0 1 2
fr 2 4 1 0 1
fr 3 5 2 1 0Then the counting pass, with minReachable starting at n = 4:
| City i | shortest dists | within ≤ 4 | count | best after (min, index) |
|---|---|---|---|---|
| 0 | 3, 4, 5 | to 1, to 2 | 2 | 2 ≤ 4 → city 0 |
| 1 | 3, 1, 2 | to 0, 2, 3 | 3 | 3 > 2 → still city 0 |
| 2 | 4, 1, 1 | to 0, 1, 3 | 3 | 3 > 2 → still city 0 |
| 3 | 5, 2, 1 | to 1, to 2 | 2 | 2 ≤ 2 → city 3 |
City 3 ties city 0 at count 2, and because the test is <=, the later index wins. Answer: 3.
Complexity
| Approach | Time | Space | Why |
|---|---|---|---|
| Repeated Dijkstra (array scan) | O(n³) | O(n²) | n sources × O(n²) select-min each |
| Repeated Dijkstra (binary heap) | O(n · E log n) | O(n + E) | better on sparse graphs |
| Floyd-Warshall | O(n³) | O(n²) | triple loop over k, i, j |
The three nested loops each run n times, giving O(n³). The dist matrix is the O(n²) space cost. The final counting pass is another O(n²) — dominated by the cubic sweep. With n ≤ 100, that's ~10⁶ operations: instant, and far easier to code correctly than juggling n separate Dijkstra runs.
Common mistakes
- Wrong loop order.
k(the intermediate) must be the outermost loop. Puttingiorjoutsidekbreaks the DP — you'd relax against distances that aren't finalized yet and get wrong shortest paths. - Using
<for the tie-break. The problem wants the largest index on a tie.count <= minReachablewith the assignment inside makes later indices overwrite;<returns the smallest index instead. - Forgetting the graph is undirected. Seed both
dist[u][v]anddist[v][u]. Seeding one direction silently makes half the routes unreachable. - Skipping the
i !== jguard when counting. Everydist[i][i]is 0, which is<= threshold, so a city would count itself and inflate every count by one. - Counting
Infinitydistances. Unreachable pairs stayInfinity; the<= thresholdcheck already excludes them, but only if you never reset them to a large finite sentinel that slips under the threshold.
Where this pattern shows up next
Floyd-Warshall is the "small dense graph, all pairs" tool, but reachability and shortest-path reasoning generalize widely:
- Find if Path Exists in Graph — pure connectivity, the yes/no version of "can
ireachj." - All Paths From Source to Target — enumerate routes instead of measuring the shortest one.
- Max Area of Island — grid traversal where a flood fill counts a connected region.
- Redundant Connection — union-find on edges, the other classic dense-graph structural question.
To watch the distance matrix relax cell by cell and the reachability counts settle, step through the Find the City with Smallest Neighbors visualizer.
FAQ
Why use Floyd-Warshall instead of running Dijkstra from each city?
Both are O(n³) on the array-scan version, but Floyd-Warshall is dramatically simpler to write: three nested loops and one min comparison, no priority queue, no per-source reset, no visited bookkeeping. For the constraint here (n ≤ 100) the cubic cost is negligible, so the win is purely correctness-under-pressure. Repeated Dijkstra with a binary heap only pulls ahead when the graph is large and sparse, where O(n · E log n) beats O(n³).
Why must the k loop be the outermost of the three?
k is the dynamic-programming dimension — it represents "which cities are allowed as intermediate stops." Sweeping k from 0 to n-1 progressively unlocks each vertex as a waypoint, and every relaxation dist[i][k] + dist[k][j] relies on those two sub-distances already being optimal for the current set of allowed intermediates. If i or j were outermost, you'd relax against partially-computed values and produce incorrect shortest paths.
How does the tie-break return the city with the largest index?
The counting loop runs i from 0 upward and updates the best city whenever count <= minReachable — note the <=, not <. Because it scans in increasing order, a later city with the same minimum count will pass the <= test and overwrite resultCity. So among all cities sharing the smallest reachable count, the one with the greatest index is the last to win, exactly as the problem requires.
What stops a city from counting itself as a neighbor?
Two guards. The diagonal dist[i][i] is initialized to 0, which would always satisfy <= distanceThreshold, so the counting loop explicitly skips it with if (i !== j). Without that check, every city's neighbor count would be inflated by one — harmless to the final ranking since it shifts all counts equally, but it would report the wrong absolute counts and break any test that checks them.
Make it stick: run this one yourself
Don't just read it — step through it interactively, one state change at a time.