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)