Floyd Warshall Algorithm

MediumShortest paths Dynamic programming

+10

A directed graph with n nodes, numbered 0 to n-1, is given as an n by n matrix: matrix[i][j] is the weight of the edge from node i to node j, or -1 when there is none, and matrix[i][i] is 0. A path's length is the sum of its edge weights.

Return an n by n matrix whose entry [i][j] is the length of the shortest path from node i to node j, or -1 when node j cannot be reached from node i.

Function

shortestDistances(matrix: integer-2d-array) → integer-2d-array

matrixinteger-2d-array: the edge weights: matrix[i][j] is the weight of the edge from i to j, or -1 when there is none
Returnsinteger-2d-array: the shortest distance for every pair of nodes, -1 where there is no path

Constraints

1 ≤ n ≤ 100, where n = matrix.length = matrix[i].length
matrix[i][i] = 0
For i ≠ j, matrix[i][j] is -1 (no edge) or 0 ≤ matrix[i][j] ≤ 1000.
Edges are one way: matrix[i][j] and matrix[j][i] are independent.

Examples

Input: matrix = [[0, 4, 11, -1], [-1, 0, 2, 9], [1, -1, 0, 3], [-1, -1, -1, 0]]
Output: [[0, 4, 6, 9], [3, 0, 2, 5], [1, 5, 0, 3], [-1, -1, -1, 0]]
Explanation: Through node 1, node 0 reaches node 2 for 6 instead of 11, and node 3 for 9. Node 1 reaches node 0 through node 2 for 3. Nothing leaves node 3, so its row is -1 off the diagonal.

Input: matrix = [[0, 6, 1], [-1, 0, -1], [-1, 0, 0]]
Output: [[0, 1, 1], [-1, 0, -1], [-1, 0, 0]]
Explanation: The edge from 2 to 1 weighs 0, so 0 → 2 → 1 costs 1, less than the direct 6. No edge leaves node 1 or enters node 0, so those pairs stay -1.

Follow-up

After you build the table, one edge gets cheaper. Can you update every distance in O(n²) instead of running the O(n³) loops again?

Hints

Open them one at a time. Each one gives away a little more.

0 of 3 opened

Solution

You need the shortest path for every pair of nodes. Floyd-Warshall finds all n² answers with one triple loop. Each round lets routes stop at one more node and costs one comparison per pair: the best route so far against the route through the new node.

Extend every route by one edge until nothing changes

Correct, but does not finish on the largest tests

Intuition

Start from the matrix and, in each pass, extend every route by one edge: a route from i to m plus the edge m → j is a route from i to j, kept if it is shorter. Repeat until a pass changes nothing.

After p passes, every shortest route of up to p+1 edges is found. No weight is negative, so some shortest route has no loop and at most n-1 edges, and the passes stop with every distance final. A pass is n³ = 10^6 steps for 100 nodes, and a long chain of shortest routes needs up to n passes: O(n⁴), up to 10^8 steps.

Algorithm

Copy matrix into dist.
For every i, m and j: if dist[i][m] and matrix[m][j] both exist, compute their sum.
If dist[i][j] is -1 or larger than the sum, store the sum and remember that the pass changed something.
Repeat the pass until it changes nothing, then return dist.

def shortestDistances(matrix):
    n = len(matrix)
    # dist starts as the routes of one edge; -1 means no route found yet.
    dist = [row[:] for row in matrix]
    changed = True
    while changed:
        changed = False
        # One pass: a route from i that ends at m may grow by the edge m -> j.
        for i in range(n):
            for m in range(n):
                if dist[i][m] == -1:
                    continue
                for j in range(n):
                    edge = matrix[m][j]
                    if edge == -1:
                        continue
                    via = dist[i][m] + edge
                    if dist[i][j] == -1 or via < dist[i][j]:
                        dist[i][j] = via
                        changed = True
    return dist

Floyd-Warshall: allow one more stop per round

Intuition

Limit which nodes a route may stop at between its ends. The table starts as the matrix, the routes with no stops. After round k, dist[i][j] is the shortest route whose stops all lie among nodes 0 to k, and the last round gives the answer.

In round k, the best route that may also stop at k either skips k, and the table already holds it, or passes k once, since no weight is negative. Its two halves stop only at nodes 0 to k-1, so they are dist[i][k] and dist[k][j].

In the first example, round 1 replaces the direct 11 from node 0 to node 2 with 6. Round 2 gives node 0 to node 3 as 6 + 3 = 9, with the stop at node 1 inside the 6.

One table is enough: row k and column k do not change in round k, because dist[k][k] is 0.

Algorithm

Copy matrix into dist; -1 means no route found yet.
For k from 0 to n-1, and for every i and j: skip the pair if dist[i][k] or dist[k][j] is -1.
Otherwise compute via = dist[i][k] + dist[k][j].
If dist[i][j] is -1 or larger than via, set it to via.
Return dist.

def shortestDistances(matrix):
    n = len(matrix)
    # dist starts as the direct edges; -1 means no route found yet.
    dist = [row[:] for row in matrix]
    # After round k, dist[i][j] is the cheapest route whose stops all lie in 0..k.
    for k in range(n):
        for i in range(n):
            if dist[i][k] == -1:
                continue
            for j in range(n):
                if dist[k][j] == -1:
                    continue
                via = dist[i][k] + dist[k][j]
                if dist[i][j] == -1 or via < dist[i][j]:
                    dist[i][j] = via
    return dist

Pitfalls and edge cases

Adding -1 as if it were a weight: -1 + 5 = 4 looks like a route. Check both parts first, and treat a -1 in dist[i][j] as worse than any route.
Putting the loop over k inside. Routes through stops 0 to k-1 must be final before node k is offered.
Using the largest int as infinity: adding two overflows a 32-bit int to a negative distance. A real distance is at most 99 × 1000 = 99,000, so 10^9 is safe, since 2 × 10^9 is below 2^31-1.
Assuming edges go both ways. In the second example node 0 reaches node 1, but node 1 reaches nothing.
Running breadth-first search, which ignores weights: in the first example it reports 11 from node 0 to node 2, not 6.

Frequently asked questions3

What is the time complexity of the Floyd Warshall algorithm?

O(n³) time for n nodes: three nested loops over the nodes, with one addition and one comparison per step, 10^6 steps for 100 nodes. The space is O(n²) for the distance table, which can be updated in place.

Does Floyd Warshall work with negative edge weights?

Yes, as long as there is no negative cycle, a loop whose weights add up to less than 0. With a negative cycle shortest paths are not defined, and the table shows it: some dist[i][i] ends below 0.

When should you use Floyd Warshall instead of Dijkstra's algorithm?

Use Floyd-Warshall for every pair of nodes in a dense graph of up to a few hundred nodes. Dijkstra from every node costs O(n³) with an array and O(n · E log n) with a heap, which wins on large sparse graphs. Floyd-Warshall needs no heap and accepts negative edges, which Dijkstra does not.

def shortestDistances(matrix):
    # Write code here

Test #1

Test #2

Argument

matrix = [[0, 4, 11, -1], [-1, 0, 2, 9], [1, -1, 0, 3], [-1, -1, -1, 0]]

Expected Output

[[0, 4, 6, 9], [3, 0, 2, 5], [1, 5, 0, 3], [-1, -1, -1, 0]]