fork download
copy 
  1. import heapq
  2. import math
  3.  
  4. def path_print(p, destination):
  5.     if p[destination] == destination:
  6.         print(destination, end = " ")
  7.     else:
  8.         path_print(p, p[destination])
  9.         print(destination, end = " ")
  10.  
  11.  
  12. def dijkstra(graph, source):
  13.     v = len(graph)
  14.     d = [math.inf] * v
  15.     p = [None] * v
  16.     fop = [0] * v
  17.  
  18.     heap = []
  19.  
  20.     d[source] = 0
  21.     p[source] = source
  22.  
  23.     heapq.heappush(heap, (d[source], source))
  24.  
  25.     while len(heap) > 0:
  26.         distance, current_node = heapq.heappop(heap)
  27.  
  28.         if fop[current_node] == 1:
  29.             continue
  30.  
  31.         fop[current_node] = 1
  32.  
  33.         for neighbor, cost in graph[current_node]:
  34.  
  35.             if fop[neighbor] == 1:
  36.                 continue
  37.  
  38.             if d[neighbor] > d[current_node] + cost:
  39.                 d[neighbor] = d[current_node] + cost
  40.                 heapq.heappush(heap, (d[neighbor], neighbor))
  41.                 p[neighbor] = current_node
  42.  
  43.  
  44.     path_print(p, 2)
  45.  
  46. graph = {
  47.     0: [(1, 2), (2, 10)],
  48.     1: [(2, 4)],
  49.     2: []
  50.     }
  51.  
  52. dijkstra(graph, 0)
  53.  
  54.  
Success #stdin #stdout 0.07s 14116KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0 1 2
https://ideone.com/cWUxc6
language:
Python 3 (python  3.12)
created:
3 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!