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,050 points
48 views

1 answer to this question.

Your answer

Your name to display (optional):
Privacy: Your email address will only be used for sending these notifications.
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,500 points

Related Questions In Python

0 votes
1 answer

Is there a foreach function in python and is there a way to implement it if there isnt any

Every occurence of "foreach" I've seen (PHP, ...READ MORE

answered Aug 31, 2018 in Python by charlie_brown
• 7,710 points
43 views
0 votes
1 answer

How to find index from raw and column in python?

You probably want to use np.ravel_multi_index: import numpy as ...READ MORE

answered Sep 12, 2018 in Python by Priyaj
• 56,120 points
47 views
0 votes
1 answer

How to find index from raw and column in python?

You probably want to use np.ravel_multi_index: import numpy as ...READ MORE

answered Sep 24, 2018 in Python by Priyaj
• 56,120 points
19 views
0 votes
1 answer

I'm using Python 2.7 to convert an XML response (from a REST call to Atlassian Fisheye) into an HTML table.

You don't have a template matching tabularQueryResult in your ...READ MORE

answered Oct 4, 2018 in Python by Priyaj
• 56,120 points
14 views
0 votes
1 answer

how can i count the items in a list?

suppose you have a list a = [0,1,2,3,4,5,6,7,8,9,10] now ...READ MORE

answered May 2 in Python by Mohammad
• 1,400 points
24 views
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 in Python by Nymeria
• 3,500 points
16 views
0 votes
1 answer

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

You don't need to change your existing ...READ MORE

answered Dec 3, 2018 in Python by Nymeria
• 3,500 points

edited Dec 19, 2018 by Nymeria 3,914 views

© 2018 Brain4ce Education Solutions Pvt. Ltd. All rights Reserved.
"PMP®","PMI®", "PMI-ACP®" and "PMBOK®" are registered marks of the Project Management Institute, Inc. MongoDB®, Mongo and the leaf logo are the registered trademarks of MongoDB, Inc.