Pattern visualizer
Find the City with Fewest Reachable Neighbors
The road weights only matter through the shortest total distance between every pair of cities, so the first job is an all-pairs shortest-path table — Floyd-Warshall, since n is small: let every city get one turn as an allowed waypoint, and let paths route through it if that shortens anything. Once every dist[i][j] is final, walk the cities in order and count how many others each one reaches within the threshold. Keep the smallest count seen, using <= rather than < when comparing — since ties are then overwritten by the later (larger) label automatically, no extra tie-break logic is needed. Animated on: 4 cities, weighted roads 0-1(3), 1-2(1), 1-3(4), 2-3(1), distanceThreshold = 4 — find the city that can reach the fewest other cities within that distance, preferring the larger label on a tie..
All-pairs shortest paths, then pick the city with the smallest reachable count
4 cities, roads have travel weights, threshold = 4
A city qualifies by counting how many OTHER cities it can reach within a total travel distance of 4 — not by how many roads it touches directly. City 1 for instance reaches city 3 at weight 4 only through city 2, not the direct road weighing 4. So shortest paths between every pair have to be known first.
1FUNCTION findCity(n, edges, threshold):2 dist <- n x n matrix, 0 on diagonal, INFINITY elsewhere3 FOR EACH (u, v, w) IN edges4 dist[u][v] <- w, dist[v][u] <- w5 FOR k FROM 0 TO n - 16 dist[i][j] <- MIN(dist[i][j], dist[i][k] + dist[k][j])7 FOR ALL i, j8 best <- -1, bestCount <- n9 FOR c FROM 0 TO n - 110 count <- COUNT j != c WHERE dist[c][j] <= threshold11 IF count <= bestCount12 best <- c, bestCount <- count13 RETURN best
← / → step · space play · Home restart