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