Bellman-Ford After K Rounds

Problem

Run exactly k rounds of Bellman-Ford relaxation and report the resulting tentative distances.

edges is a list of directed [u, v, w] triples with possibly negative w, and rounds is a non-negative integer. Each round relaxes every edge in the given order in place, so later edges in the same round see earlier updates. Return -1 for nodes whose distance is still infinite; no early stopping is allowed.

Hint

Relax in place: the edge order inside a round genuinely changes the final array.

Test cases

case 1

in: [5,[[0,1,6],[0,2,7],[1,2,8],[1,3,5],[1,4,-4],[2,3,-3],[2,4,9],[3,1,-2],[4,0,2],[4,3,7]],0,1]

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

case 2

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

expected: [0,-1,-1]

case 3

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

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

case 4

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

expected: [0,2,4]

Starter codePython

def bellman_ford_after_rounds(n, edges, source, rounds):
    # Your code here
    pass

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