Shortest path from source to and from a negative cycle using Bellman Ford in Python

Question

 would like to find the shortest path from a source node in the graph to a negative cycle without walking over any cycle twice. If there is a definitive answer to this, please answer. Otherwise, I would like to show how I have approached the problem in the hope that others may show me where I have erred.

Answer 1

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