Implement Bellman-Ford and Floyd-WarshallStep 5 of 5

Query the matrix

12345

Step 5: Query the matrix

With the all-pairs matrix in hand, a lookup is a single indexing operation. Wrap it so callers do not touch the matrix directly.

Implement shortest(dist_matrix, u, v). dist_matrix is the n by n result of floyd_warshall. Return the shortest distance from u to v, which is simply dist_matrix[u][v]. That value is already float('inf') when v is unreachable from u and 0 when u == v, so no special cases are needed.

All earlier functions are provided; you only need the one-line lookup.

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):
    INF = float('inf')
    dist = [[INF] * n for _ in range(n)]
    for i in range(n):
        dist[i][i] = 0
    for u, v, w in edges:
        if w < dist[u][v]:
            dist[u][v] = w
    for k in range(n):
        for i in range(n):
            if dist[i][k] == INF:
                continue
            for j in range(n):
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
    return dist


def shortest(dist_matrix, u, v):
    """Return the shortest distance from u to v held in dist_matrix."""
    # TODO: index into the matrix and return the value.
    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.

PreviousAll challenges