# Dijkstra's algorithm for shortest paths
# along the lines in Gerez' book
# NvdM
# can't use v.distance, since v's are string.
# converting v's to class/struct also requires pretty printing
    # D = {}    # dictionary of final distances, with vertex as key and distance

import sys

def Dijkstra (G, start, end = None, animate=0):
    # G[v] is a dict of distances keyed by vertices adjacent to v
    # G[v][u] is the distance from v to u if u is adjacent to v
    T = set ()  # set of vertices for which min distance is known.
    D = dict () # dictionary of final distances,
                # with vertex as key and distance as value

    V = G.keys () # set which is initialized to all vertices.

    T.add (start)
    V.remove (start)

    # initialize all distances
    D[start] = 0
    for v in V:
        D[v] = sys.maxint

    for v in G[start]: # loop over all vertices reachable from start
        D [v] = G[start][v]

    while end not in T and len (V) > 0:
        if animate: print "T", T, "\n", "D", D
        u  = closest (D, V) # find closest vertex to start, among those in V
        T.add (u)
        V.remove (u)
        for v in G[u]:
            if D [v] > G[u][v] + D[u]:
                D [v] = G[u][v] + D[u]

    return D

def closest (D, V):
    d = sys.maxint
    c = None
    for v in V:
        if D[v] < d:
            c, d = v, D[v]
    return c

G = {'v1': {'v2': 6, 'v4': 1, 'v5': 3},
     'v2': {'v3': 1, 'v4': 2},
     'v3': {},
     'v4': {'v3': 5, 'v5': 1},
     'v5': {'v6': 1},
     'v6': {'v1': 2, 'v2': 1}}

print Dijkstra(G, 'v1', animate=1)

# example, CLR p.528
G = {'s': {'u':10, 'x':5},
    'u': {'v':1, 'x':2},
    'v': {'y':4},
    'x':{'u':3,'v':9,'y':2},
    'y':{'s':7,'v':6}}

# print Dijkstra(G, 's', animate=1)


# print shortestPath (G,'s','v')