Bellman-Ford Shortest Paths

Problem

Given n nodes, directed edges as [u, v, w] triples that may include negative weights, and a source node, return the shortest distance from the source to every node, using -1 for unreachable nodes.

Relax every edge n - 1 times, stopping early when a full pass makes no change. Assume there are no negative-weight cycles reachable from the source.

Hint

In the worst case each relaxation round extends the shortest path by one edge.

Test cases

case 1

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

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

case 2

in: [1,[],0]

expected: [0]

case 3

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

expected: [0,5]

case 4

in: [3,[],2]

expected: [-1,-1,0]

case 5

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

expected: [0,3,1]

Starter codePython

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

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