Floyd-Warshall After Vertex k

Problem

Return the Floyd-Warshall distance matrix after allowing only intermediate vertices 0 through k.

Start from the direct-edge distance matrix and run the main triple loop with mid ranging over 0..k inclusive; k = -1 means no intermediate vertex has been processed yet. edges is an undirected [u, v, w] list with positive weights. Report -1 for pairs that are still unreachable.

Hint

Processing vertex k early can still change distances because smaller intermediates chain together.

Test cases

case 1

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

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

case 2

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

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

case 3

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

expected: [[0,3],[3,0]]

case 4

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

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

case 5

in: [1,[],-1]

expected: [[0]]

Starter codePython

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

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