Katkat
Back

Detect a Reachable Negative Cycle

Hive.AiSoftware Engineer · Technical Screen
HardSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests the implementation of the Bellman-Ford algorithm to identify negative cycles reachable from a source vertex, specifically requiring careful handling of unreachable nodes to avoid incorrect cycle detection.

Problem Statement

Given a directed graph with n vertices (indexed 0 to n-1) and a list of weighted edges edges where each edge is represented as (u, v, weight), determine if there exists a negative-weight cycle reachable from a given source vertex start_node.

A negative-weight cycle is a path where the sum of edge weights is less than zero and the path starts and ends at the same vertex. You must ensure the cycle is reachable from the start_node.

Function Signature

def has_reachable_negative_cycle(n: int, edges: list[tuple[int, int, int]], start_node: int) -> bool:

Constraints

  • 1 <= n <= 1000
  • 0 <= len(edges) <= 5000
  • -1000 <= weight <= 1000
  • The graph may contain self-loops and parallel edges.

Examples

Example 1: Input: n = 3, edges = [(0, 1, 1), (1, 2, -5), (2, 1, 2)], start_node = 0 Output: True Explanation: There is a cycle 1 -> 2 -> 1 with a total weight of -3, which is reachable from node 0.

Example 2: Input: n = 3, edges = [(0, 1, 5), (1, 2, -10), (2, 0, 5)], start_node = 2 Output: True Explanation: The cycle 2 -> 0 -> 1 -> 2 has weight 0, not negative. However, if the edge (1, 2, -10) were replaced with (1, 2, -20), it would be negative.

Edge Cases

  • Disconnected components: Only cycles reachable from start_node should count.
  • n = 1 with a negative self-loop.
  • Parallel edges: Handle multiple edges between the same two nodes.

Hints

Hint 1

Initialize distances to infinity, but ensure `dist[start_node] = 0` to distinguish reachable nodes from unreachable ones.

Hint 2

Perform the relaxation step `n-1` times, then perform an extra pass: any edge `(u, v)` where `dist[u] + weight < dist[v]` and `dist[u]` is not infinity indicates a cycle.

Hint 3

If you detect a node `v` that can still be relaxed after `n-1` iterations, ensure you only return True if `v` is reachable from the source.

Follow-up questions

  • How would you recover the specific nodes involved in the negative cycle if one is found?
  • What is the time and space complexity of your solution, and can it be optimized using the SPFA (Shortest Path Faster Algorithm) variation?
  • How does the algorithm behave if the graph contains edges with weight 0 or positive cycles?