 # most_reliable_path_modified_Dijkstra

Aug 9th, 2022 (edited)
677
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. from collections import deque
2. from queue import PriorityQueue
3.
4.
5. class Edge:
6.     def __init__(self, first, second, weight):
7.         self.first = first
8.         self.second = second
9.         self.weight = weight
10.
11.
12. nodes = int(input())
13. edges = int(input())
14.
15. graph = [[] for _ in range(nodes)]
16.
17. for _ in range(edges):
18.     first, second, weight = [int(x) for x in input().split()]
19.     edge = Edge(first, second, weight)
20.     graph[first].append(edge)
21.     graph[second].append(edge)
22.
23. start_node = int(input())
24. end_node = int(input())
25.
26. pq = PriorityQueue()
27. pq.put((-100, start_node))
28.
29. distance = [float('-inf')] * nodes
30. distance[start_node] = 100
31.
32. parent = [None] * nodes
33.
34. while not pq.empty():
35.     max_distance, node = pq.get()
36.     if node == end_node:
37.         break
38.     for edge in graph[node]:
39.         child = edge.second if edge.first == node else edge.first
40.         new_distance = -max_distance * edge.weight/100
41.         if new_distance > distance[child]:
42.             distance[child] = new_distance
43.             parent[child] = node
44.             pq.put((-new_distance, child))
45.
46. print(f'Most reliable path reliability: {distance[end_node]:.2f}%')
47. path = deque()
48. node = end_node
49. while node is not None:
50.     path.appendleft(node)
51.     node = parent[node]
52. print(*path, sep=' -> ')