In [8]:

    

def update(G, cost, parent):
    # O(|V||E|)
    for vertex in G.keys():
        for neighbor, distance in G[vertex]:
            if cost[vertex] + distance < cost[neighbor]:
                cost[neighbor] = cost[vertex] + distance
                parent[neighbor] = vertex

def shortest_path(G, root):
    cost = {v:10000 for v in G.keys()}
    cost[root] = 0
    parent = {v:None for v in G.keys()}
    for i in range(len(G)-1):
        update(G, cost, parent)
        
    return cost, parent
        
        
        
G = {0:[(1, 8), (2, 10)], 1:[(3, 1)], 2:[(5, 2)], 3:[(2, -4), (5, -1)], 4:[(2, 1)], 5:[(4, -2)] }
cost, parent = shortest_path(G, 0)
print cost
print parent


    

    




{0: 0, 1: 8, 2: 5, 3: 9, 4: 5, 5: 7}
{0: None, 1: 0, 2: 3, 3: 1, 4: 5, 5: 2}