class NegativeWeightFinder:
def __init__(self, graph: nx.Graph):
self.graph = graph
self.predecessor_to = {}
self.distance_to = {}
def initialize(self, source):
for node in self.graph:
# Initialize all distance_to values to infinity and all predecessor_to values to None
self.distance_to[node] = float('Inf')
self.predecessor_to[node] = None
# The distance from any node to (itself) == 0
self.distance_to[source] = 0
def bellman_ford(self, source):
self.initialize(source)
for i in range(len(self.graph) - 1):
for edge in self.graph.edges(data=True):
self.relax(edge)
for edge in self.graph.edges(data=True):
if self.distance_to[edge[0]] + edge[2]['weight'] <
self.distance_to[edge[1]]:
yield self._retrace_negative_loop(edge[1])

I have also implemented a method to retrace negative loops:

def _retrace_negative_loop(self, start):
loop = [start]
while True:
next_node = self.predecessor_to[next_node]
# if negative cycle is complete
if next_node in loop:
loop = loop[:loop.index(next_node) + 1]
loop.insert(0, next_node)
return loop