Floyd-Warshall Small

Problem

Compute all-pairs shortest paths in an undirected weighted graph with the Floyd-Warshall algorithm.

edges is a list of [u, v, w] triples with w > 0. Return an n by n matrix of shortest distances, using -1 for unreachable pairs and 0 on the diagonal.

Hint

Try every intermediate node k between every pair i, j.

case 1

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

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

case 2

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

expected: [[0,5],[5,0]]

case 3

in: [3,[]]

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

case 4

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

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

Starter codePython

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

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