SPFA Shortest Path

Problem

Compute single-source shortest paths with the SPFA queue-based relaxation.

edges is a list of directed [u, v, w] triples. Return [distances, relax_count] where distances use -1 for unreachable nodes and relax_count counts successful relaxations. Nodes are re-enqueued only when they are not already in the queue.

Hint

SPFA is Bellman-Ford with a queue, often much faster in practice.

Test cases

case 1

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

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

case 2

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

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

case 3

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

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

Starter codePython

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

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