Dijkstra in Python

Dijkstra in Py3 using MinHeap and DP


  • #JustForFun
  • #DataStructures
  • #DynamicProgramming
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.
    while minHeap:
        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]