Given a directed weighted graph, determine whether any negative cycle is reachable from the source node. Pattern focus: Relaxation. After n-1 rounds, one more successful relaxation indicates a reachable negative cycle.
n = node count, edges = directed weighted edges [u, v, w], source = start node
true if a reachable negative cycle exists, otherwise false
Example 1:
Input:
n = 3 edges = [[0,1,1],[1,2,-1],[2,1,-1]] source = 0
Output:
true
Explanation:
Nodes 1 and 2 form a reachable negative cycle.
Example 2:
Input:
n = 3 edges = [[0,1,1],[1,2,2]] source = 0
Output:
false
Explanation:
There is no cycle at all.
Example 3:
Input:
n = 4 edges = [[1,2,-3],[2,1,1]] source = 0
Output:
false
Explanation:
The negative cycle is not reachable from the source.