Advertisement
viligen

dijkstra_pq

Aug 9th, 2022
479
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 1.38 KB | None | 0 0
  1. from queue import PriorityQueue
  2. from collections import deque
  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. edges = int(input())
  12. graph = {}
  13.  
  14. for _ in range(edges):
  15.     source, destination, weight = [int(x) for x in input().split(', ')]
  16.     if source not in graph:
  17.         graph[source] = []
  18.     if destination not in graph:
  19.         graph[destination] = []
  20.     graph[source].append(Edge(source, destination, weight))
  21.  
  22. start = int(input())
  23. target = int(input())
  24. max_node = max(graph.keys())
  25. distance = [float('inf')] * (max_node + 1)
  26. parent = [None] * (max_node + 1)
  27.  
  28. distance[start] = 0
  29.  
  30. pq = PriorityQueue()
  31. pq.put((0, start))
  32.  
  33. while not pq.empty():
  34.     min_dist, node = pq.get()
  35.     if node == target:
  36.         break
  37.     for edge in graph[node]:
  38.         new_distance = min_dist + edge.weight
  39.         if new_distance < distance[edge.destination]:
  40.             distance[edge.destination] = new_distance
  41.             parent[edge.destination] = node
  42.             pq.put((new_distance, edge.destination))
  43.  
  44. if distance[target] == float('inf'):
  45.     print('There is no such path.')
  46. else:
  47.     print(distance[target])
  48.  
  49.     path = deque()
  50.     node = target
  51.     while node is not None:
  52.         path.appendleft(node)
  53.         node = parent[node]
  54.     print(*path)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement