fork download
copy 
  1. from queue import PriorityQueue
  2. import math
  3.  
  4. def print_path(parent, destination):
  5.     if parent[destination] == destination:
  6.         print(destination, end = " ")
  7.     else:
  8.         print_path(parent, parent[destination])
  9.         print(destination, end = " ")
  10.  
  11. def dijkstra(graph, source, V):
  12.     distance = [math.inf]*V
  13.     parent = [-1] * V
  14.     found_optimal = [0] * V
  15.  
  16.     pq = PriorityQueue()
  17.  
  18.     distance[source] = 0
  19.     pq.put((distance[source], source))
  20.     parent[source] = source
  21.  
  22.     while not pq.empty():
  23.         current_node = pq.get()[1]
  24.         if found_optimal[current_node] == 1:
  25.             continue
  26.         found_optimal[current_node] = 1
  27.  
  28.         for neighbor, cost in graph[current_node]:
  29.             if found_optimal[neighbor] != 1:
  30.                 if distance[neighbor] > distance[current_node] + cost:
  31.                     distance[neighbor] = distance[current_node] + cost
  32.                     pq.put((distance[neighbor], neighbor))
  33.                     parent[neighbor] = current_node
  34.  
  35.     for i in range(V):
  36.         print_path(parent, i)
  37.         print()
  38.  
  39.  
  40.  
  41.  
  42.  
  43.  
  44. graph = {
  45.     0 : [(1, 5), (2, 4)],
  46.     1 : [(2, 2), (3, 10)],
  47.     2 : [(3, 7)],
  48.     3 : []
  49.     }
  50.  
  51. V = 4
  52.  
  53. source = 0
  54.  
  55. dijkstra(graph, source, V)
  56.  
  57.  
  58.  
  59.  
  60.  
  61.  
  62.  
  63.  
  64.  
Success #stdin #stdout 0.14s 13968KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0 
0 1 
0 2 
0 2 3
https://ideone.com/rFAQq8
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!