Skip to content
Hello Python

Compute All-Pairs Shortest Paths

Practice ExerciseIntermediateMediumGraphMatrix / GridFloyd-Warshall

Checking your account…

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

Loading the interactive Practice workspace.If it does not appear, the problem and learning material remain readable, but browser execution is unavailable.Reload Practice workspace

Problem

Implement all_pairs_shortest_paths(matrix). matrix uses 0 on the diagonal and -1 for absent directed edges. Return a new shortest-distance matrix with -1 for unreachable pairs.

Starter code

def all_pairs_shortest_paths(matrix):
    pass
Test cases

via-middle

{
  "args": [
    [
      [
        0,
        3,
        -1
      ],
      [
        -1,
        0,
        2
      ],
      [
        1,
        -1,
        0
      ]
    ]
  ]
}

Expected: [[0,3,5],[3,0,2],[1,4,0]]

disconnected

{
  "args": [
    [
      [
        0,
        -1
      ],
      [
        -1,
        0
      ]
    ]
  ]
}

Expected: [[0,-1],[-1,0]]

Wizard outline
  1. Step 1: Normalize the distance matrix

    Copy the matrix and represent -1 edges as infinity. Min comparisons need a numeric unreachable sentinel.

  2. Step 2: Allow node 0 as an intermediate

    Compare each direct path with the path through node 0. Floyd-Warshall grows the allowed-intermediate set one node at a time.

  3. Step 3: Expand through every intermediate

    Repeat the matrix relaxation for every possible middle node. After middle k, distances may use only intermediates 0 through k.

Footguns and prerequisites
  • Adding through an unreachable segment invents a path.
  • Updating the caller matrix violates the new-result contract.
  • trees and graphs
Reviewed references
Recommended approach and implementation

Copy the matrix, convert absent edges to infinity, and apply the intermediate-vertex recurrence in k-first order.

Why it works: 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.

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]