import heapq

def dijkstra(adj, costs, s, t):    
    Q = []     # priority queue of items; note item is mutable.
    d = {s: 0} # vertex -> minimal distance
    Qd = {}    # vertex -> [d[v], parent_v, v]
    p = {}     # predecessor
    visited_set = set([s])

    for v in adj.get(s, []):
        d[v] = costs[s, v]
        item = [d[v], s, v]
        heapq.heappush(Q, item)
        Qd[v] = item

    while Q:
        cost, parent, u = heapq.heappop(Q)
        if u not in visited_set:
            fout.write('visit:'+str(u)+", ")
            p[u]= parent
            visited_set.add(u)
            if u == t:
                return p, d[u]
            for v in adj.get(u, []):
                if d.get(v):
                    if d[v] > costs[u, v] + d[u]:
                        d[v] =  costs[u, v] + d[u]
                        Qd[v][0] = d[v]    # decrease key
                        Qd[v][1] = u       # update predecessor
                        heapq._siftdown(Q, 0, Q.index(Qd[v]))
                else:
                    d[v] = costs[u, v] + d[u]
                    item = [d[v], u, v]
                    heapq.heappush(Q, item)
                    Qd[v] = item

    return None

def make_undirected(cost):
    ucost = {}
    for k, w in cost.iteritems():
        ucost[k] = w
        ucost[(k[1],k[0])] = w
    return ucost

if __name__=='__main__':

    """# adjacent list
    adj = { 1: [2,3,6],
            2: [1,3,4],
            3: [1,2,4,6],
            4: [2,3,5,7],
            5: [4,6,7],
            6: [1,3,5,7],
            7: [4,5,6]}

    # edge costs
    cost = { (1,2):7,
            (1,3):9,
            (1,6):14,
            (2,3):10,
            (2,4):15,
            (3,4):11,
            (3,6):2,
            (4,5):6,
            (5,6):9,
            (4,7):2,
            (5,7):1,
            (6,7):12}

    cost = make_undirected(cost)

    s, t = 1, 7"""
    adj={1:[2,3,4],
         2:[1,5,6],
         3:[1,5,6,7],
         4:[1,7],
         5:[2,8],
         6:[2,3,8],
         7:[3,4,8],
         8:[5,6,7]}

    cost={ (1,2):1,
           (1,3):2,
           (1,4):5,
           (2,5):4,
           (2,6):11,
           (3,5):9,
           (3,6):5,
           (3,7):16,
           (4,7):2,
           (5,8):18,
           (6,8):13,
           (7,8):2
           }
    cost = make_undirected(cost)
    String=" "
    s, t = 1, 8
    fout=open("out_35_17_5.txt",'w')
    predecessors, min_cost = dijkstra(adj, cost, s, t)
    c = t
    path = [c]    
    String= String+"\nmin cost:"+str(min_cost)
    while predecessors.get(c):
        
        path.insert(0, predecessors[c])
        c = predecessors[c]
    String=String+"\nShortest Path:"
    for i in path:
        String=String+str(i)+","
    fout.write(String)