ZERO / HERO
Would going via this city help?

Floyd-Warshall (All-Pairs)

The analogy

You want the travel time between every pair of towns. So you go through the towns one at a time and ask a single question: "for every pair, would routing through THIS town be quicker than what I already know?" Three nested loops, and after considering every town as a possible waypoint, every pair is optimal.

Visualizer

Every pair, via every waypoint

step 1 / 10
ABCD
A03∞7
B802∞
C5∞01
D2∞∞0

A 4×4 distance matrix. Direct edges only so far — infinity means no direct road.dist[i][j] = direct edge, or infinity

def floyd_warshall(dist):
    n = len(dist)
    for k in range(n):            # k MUST be outermost
        for i in range(n):
            dik = dist[i][k]
            if dik == float("inf"):
                continue
            for j in range(n):
                if dik + dist[k][j] < dist[i][j]:
                    dist[i][j] = dik + dist[k][j]
    for i in range(n):
        if dist[i][i] < 0:
            raise ValueError("negative cycle through", i)
    return dist

# O(V^3) time, O(V^2) space. Negative edges fine.
Check yourself

What breaks if you make k the innermost loop?