def dijkstra(g, source): dist = [99999] * len(g) # initialize dist for all to infinity dist[source] = 0 # dist to source itself is 0 procd = 0 # the number of nodes already processed while procd < len(g): # Replace dist with a min heap for O(E log V) performance closest = -1 for i in range(len(dist)): # Find closest node if dist[i] >= 0 and (closest == -1 or dist[i] < dist[closest]): closest = i print('Distance to', closest, 'is', dist[closest]) for e in g[closest]: if dist[closest] + e[1] < dist[e[0]]: # Update distance through edges attached to closest dist[e[0]] = dist[closest] + e[1] dist[closest] = -1 # mark as visited procd += 1 # Graph in adjacency list form: # Each inner list represents the collection of edges attached to the node # An edge pair (n,w) represents n, the other node, and w, the weight # Nodes are represented by their index in the list graph = [[(2,5), (3,8)], [(3,3), (4,6), (5,2)], [(0,5), (3,2), (4,3)], [(0,8), (1,3), (2,2), (5,7)], [(1,6), (2,3)], [(1,2), (3,7)]] dijkstra(graph, 0)