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,060 points
77 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,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
64 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,160 points
58 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,160 points
26 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,160 points
25 views
+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 6 in Python by Neha
• 330 points

edited Jul 8 by Kalgi 127 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
37 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 6,685 views