Advertisement
viligen

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!
Python 1.29 KB | None | 0 0
  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=' -> ')
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement