Floyd-Warshall Shortest Paths

Problem

Given n nodes and directed edges as [u, v, w] triples with no negative cycles, return the n by n matrix of shortest distances, using -1 for unreachable pairs and 0 on the diagonal.

Run the Floyd-Warshall triple loop, relaxing dist[i][j] through every possible intermediate node. Parallel edges keep the smaller weight.

Hint

The middle loop is the intermediate node; skip pairs involving an infinite distance.

Test cases

case 1

in: [4,[[0,1,1],[0,3,4],[1,2,2],[2,3,1],[3,1,3]]]

expected: [[0,1,3,4],[-1,0,2,3],[-1,4,0,1],[-1,3,5,0]]

case 2

in: [1,[]]

expected: [[0]]

case 3

in: [2,[[0,1,5]]]

expected: [[0,5],[-1,0]]

case 4

in: [3,[[0,1,2],[1,2,3]]]

expected: [[0,2,5],[-1,0,3],[-1,-1,0]]

case 5

in: [2,[[0,1,2],[1,0,2]]]

expected: [[0,2],[2,0]]

Starter codePython

def floyd_warshall(n, edges):
    # Your code here
    pass

5 test cases · run your code against them in the editor