# Dijkstra's algorithm

# vertex
v = ['s','a','b','c','d','e','f','g','h','i','j','k']

# weight
w = {'s': {'s':  0,'a':  3,'b':999,'c':999,'d':  4,'e':999,'f':999,'g':999,'h':999,'i':999,'j':999,'k':999},
     'a': {'s':  3,'a':  0,'b':  1,'c':  1,'d':999,'e':999,'f':999,'g':999,'h':999,'i':999,'j':999,'k':999},
     'b': {'s':999,'a':  1,'b':  0,'c':999,'d':999,'e':  2,'f':  2,'g':999,'h':999,'i':999,'j':999,'k':  3},
     'c': {'s':999,'a':  1,'b':999,'c':  0,'d':999,'e':999,'f':999,'g':999,'h':999,'i':999,'j':999,'k':999},
     'd': {'s':  4,'a':999,'b':999,'c':999,'d':  0,'e':  2,'f':999,'g':999,'h':  1,'i':999,'j':999,'k':999},
     'e': {'s':999,'a':999,'b':  2,'c':999,'d':  2,'e':  0,'f':999,'g':999,'h':999,'i':999,'j':999,'k':  3},
     'f': {'s':999,'a':999,'b':  2,'c':999,'d':999,'e':999,'f':  0,'g':999,'h':999,'i':999,'j':999,'k':999},
     'g': {'s':999,'a':999,'b':999,'c':999,'d':999,'e':999,'f':999,'g':  0,'h':999,'i':999,'j':999,'k':  1},
     'h': {'s':999,'a':999,'b':999,'c':999,'d':  1,'e':999,'f':999,'g':999,'h':  0,'i':  1,'j':  2,'k':999},
     'i': {'s':999,'a':999,'b':999,'c':999,'d':999,'e':999,'f':999,'g':999,'h':  1,'i':  0,'j':999,'k':999},
     'j': {'s':999,'a':999,'b':999,'c':999,'d':999,'e':999,'f':999,'g':999,'h':  2,'i':999,'j':  0,'k':999},
     'k': {'s':999,'a':999,'b':  3,'c':999,'d':999,'e':  3,'f':999,'g':  1,'h':999,'i':999,'j':999,'k':  0}
    }

cost = w['s']
parent = ['s',]*len(v)

def keika():
    print 'cost: [',
    s = []
    for i in v:
        s.append('%3d' % cost[i])
    print ','.join(s) + ']',
    print ' parent:', parent

keika()

u = v[1:]
while len(u) <> 0:
    m = ''; c = 999
    for i in u:
        if cost[i] < c:
            m = i
            c = cost[i]
    del u[u.index(m)]
    d = []
    for i in v:
        if 0 < w[m][i] < 999:
            d.append(i)
    if not d:
        break
    for x in d:
        if c + w[m][x] < cost[x]:
            cost[x] = c + w[m][x]
            parent[v.index(x)] = m
    keika()