Bellman-Ford with Negative Edges

Problem

Compute single-source shortest paths in a directed weighted graph that may contain negative edge weights (but no negative cycles).

edges is a list of [u, v, w] triples. Relax every edge n - 1 times. Return distances from src in node order, using -1 for unreachable nodes.

Hint

n - 1 passes are enough for any shortest path without negative cycles.

case 1

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

expected: [0,1,2,4]

case 2

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

expected: [0,5,2]

case 3

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

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

case 4

in: [1,[],0]

expected: [0]

Starter codePython

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

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