City k becomes available as an intermediate point. Before this step, the table already accounts for all previously allowed intermediate cities.

A best route either avoids k, keeping the old distance, or uses k and splits into i→k and k→j. Under the no-negative-cycle condition, a best walk can be simplified enough that repeating k is unnecessary. This gives min(d[i][j], d[i][k]+d[k][j]). Initialize self-distance to zero and direct distances to minimum edge costs. The middle vertex must be outermost for this recurrence. For the city task, count other vertices within the threshold and implement its larger-index tie-break explicitly.

What the function promises: city_with_fewest takes n≥1, positive-weight undirected edges with labels 0..n−1, and a distance threshold. Return the chosen city. The included Floyd helper supports directed graphs without negative cycles and raises if any negative cycle exists.

def floyd_distances(n, edges, undirected=False):
    distance = [[float("inf")] * n for _ in range(n)]
    for i in range(n):
        distance[i][i] = 0
    for u, v, weight in edges:
        distance[u][v] = min(distance[u][v], weight)
        if undirected:
            distance[v][u] = min(distance[v][u], weight)
    for k in range(n):
        for i in range(n):
            for j in range(n):
                distance[i][j] = min(
                    distance[i][j], distance[i][k] + distance[k][j])
    if any(distance[i][i] < 0 for i in range(n)):
        raise ValueError("A negative cycle prevents finite all-pairs distances")
    return distance

def city_with_fewest(n, edges, threshold):
    distance = floyd_distances(n, edges, undirected=True)
    counts = [sum(j != i and distance[i][j] <= threshold
                  for j in range(n)) for i in range(n)]
    return min(range(n), key=lambda i: (counts[i], -i))

assert floyd_distances(3, [(0,1,8), (0,2,2), (2,1,3)])[0][1] == 5
assert city_with_fewest(3, [(0,1,1), (1,2,1)], 1) == 2
assert city_with_fewest(3, [], 1) == 2

Work and storage: O(V³ + E) time and O(V²) space. The threshold counting adds only O(V²). This is deliberately for modest vertex counts; repeated Dijkstra can be preferable on large sparse positive-weight graphs.

When to recognize it: Distances are needed between every pair. Allow one more intermediate city at a time.

Check before applying it: The intermediate-vertex loop must be outermost. O(V³) is for modest graphs; large sparse graphs may favor repeated Dijkstra.

No. Its recurrence does not finalize vertices greedily, so negative edges are allowed without negative cycles. A negative diagonal after processing signals a negative cycle; affected shortest-walk costs are not finite.