# Dijkstra's algorithm

# vertex
v = ['s','a','b','c','d','e']

# weight
w = {'s': {'s':  0,'a':999,'b':999,'c':  8,'d': 15,'e':999},
     'a': {'s': 10,'a':  0,'b': 24,'c':999,'d':  8,'e':999},
     'b': {'s':999,'a':999,'b':  0,'c':999,'d':999,'e':  6},
     'c': {'s':999,'a':999,'b':999,'c':  0,'d':  5,'e':999},
     'd': {'s':999,'a':999,'b': 12,'c':999,'d':  0,'e':  7},
     'e': {'s':999,'a':999,'b':  3,'c':999,'d':999,'e':  0}
    }

cost = w['s']
parent = ['s',]*6

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:   # <-- u
        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()