Advertisement
viligen

bellman_ford

Aug 9th, 2022
469
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 1.33 KB | None | 0 0
  1. from collections import deque
  2.  
  3.  
  4. class Edge:
  5.     def __init__(self, source, destination, weight):
  6.         self.source = source
  7.         self.destination = destination
  8.         self.weight = weight
  9.  
  10.  
  11. nodes = int(input())
  12. edges = int(input())
  13.  
  14. graph = []
  15.  
  16. for _ in range(edges):
  17.     source, destination, weight = [int(x) for x in input().split()]
  18.     graph.append(Edge(source, destination, weight))
  19.  
  20. start = int(input())
  21. target = int(input())
  22.  
  23. distance = [float('inf')] * (nodes + 1)
  24. distance[start] = 0
  25. parent = [None] * (nodes + 1)
  26.  
  27. for _ in range(nodes - 1):
  28.     update = False
  29.     for edge in graph:
  30.         if distance[edge.source] == float('inf'):
  31.             continue
  32.         new_distance = distance[edge.source] + edge.weight
  33.         if new_distance < distance[edge.destination]:
  34.             distance[edge.destination] = new_distance
  35.             parent[edge.destination] = edge.source
  36.             update = True
  37.     if not update:
  38.         break
  39.  
  40. for edge in graph:
  41.  
  42.     new_distance = distance[edge.source] + edge.weight
  43.     if new_distance < distance[edge.destination]:
  44.         print('Negative Cycle Detected')
  45.         break
  46. else:
  47.     path = deque()
  48.     node = target
  49.  
  50.     while node is not None:
  51.         path.appendleft(node)
  52.         node = parent[node]
  53.  
  54.     print(*path)
  55.     print(distance[target])
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement