Floyd-Warshall Path Reconstruction

Problem

Find a concrete shortest path between two nodes using Floyd-Warshall with a next-hop matrix.

edges is a list of [u, v, w] triples for an undirected graph with positive weights. Return the node list of a shortest path from src to dst, or [] when dst is unreachable. When src equals dst return [src].

Hint

The next-hop matrix records which first step realizes each optimal distance.

Test cases

case 1

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

expected: [0,1,2,3]

case 2

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

expected: []

case 3

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

expected: [2,1,0]

case 4

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

expected: [1]

Starter codePython

def floyd_warshall_path(n, edges, src, dst):
    # Your code here
    pass

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