Implement Bellman-Ford and Floyd-WarshallStep 4 of 5

Floyd-Warshall all-pairs

12345

Step 4: Floyd-Warshall all-pairs

When you need distances between every pair of vertices, Floyd-Warshall handles negative edges in one compact triple loop.

Implement floyd_warshall(n, edges). Return an n by n matrix (a list of n lists) where entry [i][j] is the shortest distance from i to j, float('inf') when j is unreachable from i, and 0 on the diagonal. Assume there is no negative-weight cycle.

Algorithm:

  • Build dist as an n by n grid filled with float('inf'), then set dist[i][i] = 0 for all i.
  • For every edge (u, v, w), set dist[u][v] = min(existing, w) (keep the smallest weight if edges repeat).
  • For each intermediate vertex k, then each i, then each j: if dist[i][k] + dist[k][j] < dist[i][j], set dist[i][j] to that sum. Skip rows where dist[i][k] is infinite to avoid adding onto infinity.

Return the completed matrix. Earlier functions are provided.

Hints
Starter code
def bellman_ford(n, edges, source):
    dist = [float('inf')] * n
    dist[source] = 0
    for _ in range(n - 1):
        for u, v, w in edges:
            if dist[u] != float('inf') and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
    return dist


def has_negative_cycle(n, edges):
    dist = [0] * n
    for _ in range(n - 1):
        for u, v, w in edges:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
    for u, v, w in edges:
        if dist[u] + w < dist[v]:
            return True
    return False


def bellman_ford_safe(n, edges, source):
    dist = [float('inf')] * n
    dist[source] = 0
    for _ in range(n - 1):
        for u, v, w in edges:
            if dist[u] != float('inf') and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
    neg = False
    for u, v, w in edges:
        if dist[u] != float('inf') and dist[u] + w < dist[v]:
            neg = True
            break
    return (dist, neg)


def floyd_warshall(n, edges):
    """Return an n x n matrix of all-pairs shortest distances."""
    # TODO: seed diagonal and edges, then run the k-i-j triple loop.
    pass
Write it on a laptop

The editor and the test runner need a wide screen. Open this page on a desktop browser and your progress will be waiting.

PreviousNext step