Negative Closed Walk Nodes

Problem

List the nodes that admit a closed walk of negative total weight.

Run Floyd-Warshall on the directed [u, v, w] edge list and report every node i whose final dist[i][i] is negative, which certifies a negative cycle on or reachable from i's closed walk. Return the qualifying nodes in ascending order. Return an empty list when all diagonals stay non-negative.

Hint

A negative diagonal after Floyd-Warshall can only appear through a negative cycle.

Test cases

case 1

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

expected: []

case 2

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

expected: [0,1]

case 3

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

expected: [1,2]

case 4

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

expected: [0,1,2]

case 5

in: [1,[]]

expected: []

Starter codePython

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

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