Advertisement
viligen

undefined_Bellman_Ford

Aug 9th, 2022 (edited)
737
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 1.09 KB | None | 0 0
  1. from collections import deque
  2.  
  3.  
  4. def find_path(parent, node):
  5.     result = deque()
  6.     while node is not None:
  7.         result.appendleft(node)
  8.         node = parent[node]
  9.     return result
  10.  
  11.  
  12. nodes = int(input())
  13. edges = int(input())
  14.  
  15. graph = []
  16.  
  17. for _ in range(edges):
  18.     first, second, weight = [int(x) for x in input().split()]
  19.     graph.append((first, second, weight))
  20.  
  21. source = int(input())
  22. destination = int(input())
  23.  
  24. distance = [float('inf')] * (nodes + 1)
  25. distance[source] = 0
  26. parent = [None] * (nodes + 1)
  27.  
  28. for _ in range(nodes - 1):
  29.     for first, second, weight in graph:
  30.         if distance[first] == float('inf'):
  31.             continue
  32.         new_distance = distance[first] + weight
  33.         if new_distance < distance[second]:
  34.             distance[second] = new_distance
  35.             parent[second] = first
  36.  
  37. for first, second, weight in graph:
  38.     new_distance = distance[first] + weight
  39.     if new_distance < distance[second]:
  40.         print('Undefined')
  41.         break
  42. else:
  43.     path = find_path(parent, destination)
  44.     print(*path)
  45.     print(distance[destination])
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement