Johnson's Algorithm Step

Problem

Perform the reweighting step of Johnson's algorithm on a directed weighted graph with n nodes.

Add a virtual node n joined to every node with weight 0 and run Bellman-Ford to get potentials. Then replace each edge weight w with w + pot[u] - pot[v], which makes all edge weights non-negative. Return the reweighted edge list in the original order, or [] when a negative cycle exists. edges is a list of [u, v, w] triples.

Hint

The reweighted graph has the same shortest paths but no negative edges.

Test cases

case 1

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

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

case 2

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

expected: []

case 3

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

expected: [[0,1,3],[1,2,0],[2,3,0],[0,3,6]]

case 4

in: [2,[]]

expected: []

case 5

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

expected: [[0,1,5]]

Starter codePython

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

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