In [27]:

    

import heapq
import math

def dijkstra(G, src):
    # G is an adjacency list of: v_i -> [v_j, v_k, ...]
    Q = []
    cost = {node: float('inf') for node in G.keys()}
    cost[src] = 0
    parent = {src: None}
    visited = set()
    heapq.heappush(Q, (cost[src], src))
    
    while len(Q) > 0:
        c, node = heapq.heappop(Q)
        for neighbor, distance in G[node]:
            if neighbor not in visited:
                if cost[node] + distance < cost[neighbor]:
                    cost[neighbor] = cost[node] + distance
                    parent[neighbor] = node
                    heapq.heappush(Q, (cost[neighbor], neighbor))
                    
    return cost, parent

def reconstruct_path(parent, src, target):
    node = target
    path = []
    
    while node != None:
        path.insert(0, node)
        node = parent[node]

    return path

def shortest_path(G, src, target):
    cost, parent = dijkstra(G, 0)
    return reconstruct_path(parent, 0, 3)        
                    
def main():
    G = {0: [(1, 2), (2, 1)], 1: [(3, 2)], 2: [(3, 1)], 3: []}
    path = shortest_path(G, 0, 3) 
    print path
    
if __name__ == "__main__":
    main()


    

    




[0, 2, 3]