Dijkstra's Algorithm:

Explanation: https://www.youtube.com/watch?v=C84_3EvDCM8&t=2411s

graph = {
            0:[(1,4),(2,1)],
            1:[(4,4)],
            2:[(1,2),(3,4)],
            3:[(4,4)],
            4:[]
    }

from collections import defaultdict
from heapq import *

def dj(graph,source):
    dist = defaultdict(int)
    heap = [(0,source)]
    new_dist={}
    dist[source] = 0
    for i in range(1,5):
        heappush(heap,(10000,i))
        dist[i]=10000
    visited = set()
    while len(heap):
        c_dist,c_vertex = heappop(heap)
        for nbr,cost in graph[c_vertex]:
            if c_dist+cost < dist[nbr]:
                dist[nbr] = c_dist+cost
        new_dist[c_vertex] = dist[c_vertex]
        while len(heap):
            heappop(heap)
        dist.pop(c_vertex)
        heap = [(disti,vertex) for vertex, disti in dist.items()]
        heapify(heap)

    print new_dist



dj(graph,0)