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,070 points
110 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,520 points

Related Questions In Python

0 votes
1 answer
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,720 points
79 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,520 points
67 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 226 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,520 points
67 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,520 points

edited Dec 19, 2018 by Nymeria 10,089 views