We can use Bellman-Ford: relax all edges |V|-1 times to get shortest paths, then do one more pass to find any edge that can still relax — that implies a negative-weight cycle reachable from source. To return an example cycle, follow predecessors from the relaxed node |V| steps to ensure we land inside the cycle, then walk predecessors until we repeat a node to extract the cycle.python
from collections import defaultdict, deque
def bellman_ford(edges, n, src):
"""
edges: list of (u, v, w)
n: number of vertices (0..n-1)
src: source vertex
Returns: (dist, parent, cycle)
- dist: list of distances (float('inf') if unreachable)
- parent: list of predecessors (or None)
- cycle: None if no negative cycle reachable, else list of nodes in cycle (start..end, closed)
"""
INF = float('inf')
dist = [INF]*n
parent = [None]*n
dist[src] = 0
# Relax edges |V|-1 times
for _ in range(n-1):
updated = False
for u,v,w in edges:
if dist[u] != INF and dist[u] + w < dist[v]:
dist[v] = dist[u] + w
parent[v] = u
updated = True
if not updated:
break
# Check for negative cycle
for u,v,w in edges:
if dist[u] != INF and dist[u] + w < dist[v]:
# v is affected by a negative cycle; find a node guaranteed in the cycle
x = v
for _ in range(n):
x = parent[x] if parent[x] is not None else x
# collect cycle
cycle = []
cur = x
while True:
cycle.append(cur)
cur = parent[cur]
if cur == x or cur is None:
break
cycle.reverse()
return dist, parent, cycle
return dist, parent, None
# Example usage:
# edges = [(0,1,5),(1,2,2),(2,1,-10)]
# bellman_ford(edges, 3, 0)
