All pairs

Shortest path between every pair of vertices.

The Floyd-Warshall algorithm finds the shortest paths between all pairs of nodes in a graph in one go. The output is a distance matrix.

It returns results for all pairs, not just a single source. This is useful in dense graph problems.

Distance matrix

The graph is represented as an n×n adjacency matrix. graph[i][j] is the direct edge weight from i to j; if no edge, 999 (infinity) is used.

The diagonal is zero: graph[i][i] = 0. A triple loop runs on the matrix to compute the shortest paths.

Write init_graph(). Return the 4×4 adjacency matrix. Print it with print(init_graph()).

Show example solution

def init_graph():
    # Return adjacency matrix
    return [[0, 3, 999, 7], [999, 0, 1, 999], [999, 999, 0, 2], [999, 4, 999, 0]]
print(init_graph())

Infinity value

graph[i][j] = ____ (if no edge)

Show answer

graph[i][j] = 999 (if no edge)

Next lesson: Triple loop