Dijkstra in Py3 using MinHeap and DP
from heapq import heappop, heappush
def dijkstra(graph, start_node):
dp = [None] * len(graph) # To store the precomputed results.
minHeap = [(0, start_node)] # A tuple contains path-length and node.
path_length, node = heappop(minHeap)
if dp[node] is None:
dp[node] = path_length
for nei, edge_length in graph[node].items():
if dp[nei] is None:
heappush(minHeap, (path_length + edge_length, nei))
return [0 if x is None else x for x in dp]