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