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

0 votes

 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.

Nov 13, 2018 in Python by Anirudh
• 2,090 points
1,274 views

1 answer to this question.

0 votes
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
answered Nov 13, 2018 by Nymeria
• 3,560 points

Related Questions In Python

0 votes
0 answers
–1 vote
2 answers
+1 vote
1 answer
0 votes
2 answers
+1 vote
2 answers

how can i count the items in a list?

Syntax :            list. count(value) Code: colors = ['red', 'green', ...READ MORE

answered Jul 7, 2019 in Python by Neha
• 330 points

edited Jul 8, 2019 by Kalgi 4,348 views
0 votes
1 answer
0 votes
1 answer

How to create and read from a temporary file in Python?

Hi, there is a very simple solution ...READ MORE

answered Jan 29, 2019 in Python by Nymeria
• 3,560 points
1,990 views
0 votes
3 answers

How to get the return value from a thread using python?

FWIW, the multiprocessing module has a nice interface for ...READ MORE

answered Dec 15, 2020 in Python by Roshni
• 10,520 points
107,177 views
webinar REGISTER FOR FREE WEBINAR X
REGISTER NOW
webinar_success Thank you for registering Join Edureka Meetup community for 100+ Free Webinars each month JOIN MEETUP GROUP