 # bellman_ford

Aug 9th, 2022
469
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
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])