Negative Cycle Detection

Problem

Decide whether a directed weighted graph contains any negative-weight cycle.

Initialize all distances to 0 (a virtual source joined to every node) and run n full relaxation passes. If the n-th pass still relaxes an edge, a negative cycle exists. edges is a list of [u, v, w] triples.

Hint

Starting all distances at zero makes every negative cycle reachable.

Test cases

case 1

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

expected: true

case 2

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

expected: false

case 3

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

expected: true

case 4

in: [1,[]]

expected: false

case 5

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

expected: true

Starter codePython

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

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