Skip to content
Hello Python
Algorithm1 Practice1 Interview

Floyd-Warshall

Compute all-pairs shortest paths by progressively allowing each vertex as an intermediate. Learn the algorithm's preconditions, state transition, correctness argument, Python cost model, and transfer from one focused drill to a full Interview Problem.

Recognize it when

Consider Floyd-Warshall when the prompt's constraints and required operations match this shape: Compute all-pairs shortest paths by progressively allowing each vertex as an intermediate.

Pybit demonstrates Floyd-Warshall in a professional Python interview workspace.
On this page · Store All Pair Distances

Checking your account…

Sign in to save your code and progress across devices. The lesson and problem statement remain public.

Floyd-Warshall Code Labs

Store All Pair Distances

Floyd-Warshall maintains a distance matrix for every source-target pair. Initialize zero diagonals, direct edge weights, and unreachable sentinels.

Add Intermediate Vertices One at a Time

At layer k, each pair may either avoid vertex k or travel source to k plus k to target. Both subpaths use only earlier allowed intermediates.

Trace Floyd-Warshall Layers

Reference
def floyd_layers(matrix):
    distance=[row.copy() for row in matrix];trace=[];n=len(matrix)
    for middle in range(n):
        previous=[row.copy() for row in distance]
        for source in range(n):
            for target in range(n):
                if previous[source][middle] is not None and previous[middle][target] is not None:
                    candidate=previous[source][middle]+previous[middle][target]
                    if distance[source][target] is None or candidate<distance[source][target]:distance[source][target]=candidate
        trace.append([row.copy() for row in distance])
    return trace
Practice

Implement floyd_layers(matrix). None means unreachable; return the distance matrix after each allowed intermediate vertex.

Public tests

  • Add one intermediate set per layer

Loading interactive editor.If it does not appear, the reference and starter code remain readable.Reload editor

Protect Unreachable Sums

Only add the two subpaths when both are reachable. With explicit None sentinels this guard prevents invalid arithmetic from creating fake paths.

Compute All-Pairs Distances

Reference
def all_pairs_distances(matrix):
    distance=[row.copy() for row in matrix];n=len(matrix)
    for middle in range(n):
        for source in range(n):
            for target in range(n):
                if distance[source][middle] is not None and distance[middle][target] is not None:
                    candidate=distance[source][middle]+distance[middle][target]
                    if distance[source][target] is None or candidate<distance[source][target]:distance[source][target]=candidate
    return distance
Practice

Implement all_pairs_distances(matrix). None means unreachable; return shortest distances after all intermediates.

Public tests

  • Relax through every allowed middle

Loading interactive editor.If it does not appear, the reference and starter code remain readable.Reload editor

Detect Negative Cycles on the Diagonal

After all layers, a negative distance from a vertex to itself reveals a reachable negative cycle for that component. Path reconstruction needs a next-hop or predecessor matrix updated with distances.

Explain It in an Interview

Say: “After layer k, distance[i][j] is optimal using only intermediates through k. The recurrence either skips k or joins two earlier subpaths through it.” State O(V cubed) time and O(V squared) space.

Python Version Note

Complexity & Invariants

Interview bounds depend on the stated representation, input model, and real Python operations.

OperationAverageWorstInterview note
Floyd-Warshall complete workflowO(V^3)O(V^3)Copy the matrix, convert absent edges to infinity, and apply the intermediate-vertex recurrence in k-first order.

Space

O(V^2) for the focused Compute All-Pairs Shortest Paths implementation.

Assumptions

  • After processing middle k, each entry is the best path whose internal vertices are drawn from 0..k. The recurrence chooses between excluding or including k, so the final matrix contains every shortest path.
  • The bound counts Python sorting, slicing, hashing, heap, recursion, and container-copy costs rather than treating syntax as free.

Invariants Worth Saying Aloud

  1. State the precise Floyd-Warshall invariant before coding and preserve it after every update, traversal step, or recursive return.
  2. Distances are upper bounds backed by concrete discovered paths.
  3. A finalized distance cannot later be improved under the stated weight assumptions.
  4. Interpret -1 as infinity without mutating input. Preserve this claim after every transition.
  5. Apply the k-intermediate dynamic-programming recurrence. Preserve this claim after every transition.

When To Use Or Avoid Floyd-Warshall

Use It When

  • Use Floyd-Warshall when this precondition is stated or can be proved: Edge direction and weight constraints match the relaxation and finalization rules of the chosen method.
  • Use it when this maintained state removes repeated work: Distances are upper bounds backed by concrete discovered paths.

Choose Another Tool When

  • Avoid Floyd-Warshall when this precondition is absent: Edge direction and weight constraints match the relaxation and finalization rules of the chosen method.
  • Avoid it when a simpler direct scan satisfies the constraints with less implementation risk.

Common Pitfalls

These are the mistakes most likely to survive a happy-path example and fail a boundary case.

Applying the algorithm without its precondition

Verify algorithm preconditions such as sorted input, nonnegative weights, acyclicity, or admissible heuristics before applying it.

Prevent it: State and verify this precondition before coding: Edge direction and weight constraints match the relaxation and finalization rules of the chosen method.

Avoid

def all_pairs_shortest_paths(matrix):
    pass

Use instead

def all_pairs_shortest_paths(matrix):
    size = len(matrix)
    infinity = float('inf')
    distances = [[infinity if value == -1 else value for value in row] for row in matrix]
    for middle in range(size):
        for start in range(size):
            if distances[start][middle] == infinity:
                continue
            for end in range(size):
                candidate = distances[start][middle] + distances[middle][end]
                if candidate < distances[start][end]:
                    distances[start][end] = candidate
    return [[-1 if value == infinity else value for value in row] for row in distances]

Where you will hit this: Compute All-Pairs Shortest Paths(opens in a new tab)

Breaking the state transition

Returns the input matrix without discovering a path through an intermediate vertex.

Prevent it: Preserve this proof obligation: Every recorded distance is a valid path cost, and the method eventually considers every path that could improve it.

Avoid

def all_pairs_shortest_paths(matrix):
    return [row[:] for row in matrix]

Use instead

def all_pairs_shortest_paths(matrix):
    size = len(matrix)
    infinity = float('inf')
    distances = [[infinity if value == -1 else value for value in row] for row in matrix]
    for middle in range(size):
        for start in range(size):
            if distances[start][middle] == infinity:
                continue
            for end in range(size):
                candidate = distances[start][middle] + distances[middle][end]
                if candidate < distances[start][end]:
                    distances[start][end] = candidate
    return [[-1 if value == infinity else value for value in row] for row in distances]

Where you will hit this: Compute All-Pairs Shortest Paths(opens in a new tab)

Hiding Python work in the claimed bound

Include visited state, boundary cases, recursion depth, and hidden copying costs in correctness and complexity analysis.

Prevent it: Count every sort, slice, copy, membership check, heap update, and recursive frame before claiming O(V^3).

Avoid

def all_pairs_shortest_paths(matrix):
    return [row[:] for row in matrix]

Use instead

def all_pairs_shortest_paths(matrix):
    size = len(matrix)
    infinity = float('inf')
    distances = [[infinity if value == -1 else value for value in row] for row in matrix]
    for middle in range(size):
        for start in range(size):
            if distances[start][middle] == infinity:
                continue
            for end in range(size):
                candidate = distances[start][middle] + distances[middle][end]
                if candidate < distances[start][end]:
                    distances[start][end] = candidate
    return [[-1 if value == infinity else value for value in row] for row in distances]

Where you will hit this: Lowest Common Ancestor in a BST(opens in a new tab)

Reviewed References

Official Python documentation supports language behavior. Canonical problem pages provide additional practice context.