Bellman-Ford Early Termination

Problem

Count how many relaxation passes Bellman-Ford needs before distances stop changing.

Perform up to n - 1 passes over the edge list, stopping after a pass that relaxes nothing. Return the number of passes actually executed. edges is a list of [u, v, w] triples and src is the source node.

Hint

An unfavorable edge order can force one extra wave of relaxations per hop.

Test cases

case 1

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

expected: 2

case 2

in: [1,[],0]

expected: 0

case 3

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

expected: 1

case 4

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

expected: 2

case 5

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

expected: 2

Starter codePython

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

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