Learn to solve “Find the City With the Smallest Number of Neighbors at a Threshold Distance” using Floyd Warshall or a Dijkstra-per-source loop. Simple Python, step-by-step.
Here’s the [Problem Link] to begin with.
1. Problem recap
Given
ncities numbered0 … n-1,- an undirected weighted edge list
edges = [u, v, w], - a distanceThreshold,
compute for every city how many other cities can be reached with total travel distance ≤ distanceThreshold.
Return the city that has the fewest such neighbors; if several tie, return the city with the largest index.
2. Intuition
This is an all-pairs shortest-path (APSP) task followed by a simple count:
shortest(i, j) ≤ threshold ? reachable : notTwo classic APSP strategies:
| Method | Works with | Time | Space | When to prefer |
|---|---|---|---|---|
| Floyd Warshall | dense graphs, n ≲ 400 | O(n³) | O(n²) | small/medium n |
| Run Dijkstra from every city | non-negative weights | O(n·E log n) | O(n+E) | sparse or large graphs |
Below you’ll find both fully-commented solutions.
3. Solution A – Floyd Warshall
import sys
from typing import List
class Solution:
def findTheCity(
self, n: int, edges: List[List[int]], distanceThreshold: int
) -> int:
INF = sys.maxsize
# build adjacency matrix
dist = [[INF] * n for _ in range(n)]
for u, v, w in edges:
dist[u][v] = w
dist[v][u] = w
for i in range(n):
dist[i][i] = 0
# Floyd-Warshall triple loop
for via in range(n):
for i in range(n):
for j in range(n):
if dist[i][via] != INF and dist[via][j] != INF:
dist[i][j] = min(dist[i][j], dist[i][via] + dist[via][j])
# count reachable neighbors
min_cnt, city = n + 1, -1
for i in range(n):
cnt = sum(dist[i][j] <= distanceThreshold for j in range(n))
# ≥ keeps the larger index on ties
if cnt <= min_cnt:
min_cnt, city = cnt, i
return cityComplexity O(n³) time | O(n²) memory.
4. Solution B – Dijkstra from every city
import sys, heapq
from typing import List
class Solution:
def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
# adjacency list
adj = [[] for _ in range(n)]
for u, v, w in edges:
adj[u].append((v, w))
adj[v].append((u, w))
INF = sys.maxsize
def dijkstra(src: int) -> List[int]:
dist = [INF] * n
dist[src] = 0
pq = [(0, src)]
while pq:
d, u = heapq.heappop(pq)
if d > dist[u]:
continue
for v, w in adj[u]:
nd = d + w
if nd < dist[v]:
dist[v] = nd
heapq.heappush(pq, (nd, v))
return dist
min_cnt, city = n + 1, -1
for i in range(n):
row = dijkstra(i)
cnt = sum(d <= distanceThreshold for d in row)
if cnt <= min_cnt: # “<=” keeps larger index on tie
min_cnt, city = cnt, i
return cityComplexity O(n · E log n) time | O(n + E) memory.
For sparse graphs (E ≪ n²) this is usually faster than Floyd Warshall.
5. Which one should I use?
- Small
n, dense input, or you need negative-edge support?
Go with Floyd Warshall – tiny code, deterministicO(n³). - Large
n(≈ 1 000) and sparse roads (like LeetCode’s limits)?
Prefer multi-source Dijkstra – scales roughlyO(n² log n)in practice.
Either way you’ll correctly “Find the City With the Smallest Number of Neighbors at a Threshold Distance” and ace the interview.
