Dijkstra's algorithm in python -

i trying implement dijkstra's algorithm in python using arrays. implementation.

def extract(q, w):         m=0         minimum=w[0]         in range(len(w)):                 if w[i]<minimum:                         minimum=w[i]                         m=i         return m, q[m] def dijkstra(g, s, t='b'):    q=[s]    p={s:none}    w=[0]    d={}         in g:                 d[i]=float('inf')                 q.append(i)                 w.append(d[i])         d[s]=0         s=[]         n=len(q)         while q:                 u=extract(q,w)[1]                 s.append(u)                 #w.remove(extract(q, d, w)[0])                 q.remove(u)                 v in g[u]:                         if d[v]>=d[u]+g[u][v]:                                 d[v]=d[u]+g[u][v]                                 p[v]=u         return d, p b='b' a='a' d='d' g='g' e='e' c='c' f='f' g={b:{a:5, d:1, g:2}, a:{b:5, d:3, e:12, f:5}, d:{b:1, g:1, e:1, a:3}, g:{b:2, d:1, c:2}, c:{g:2, e:1, f:16}, e:{a:12, d:1, c:1, f:2}, f:{a:5, e:2, c:16}} print "assuming start vertex b:" print "shortest distances", dijkstra(g, b)[0] print "parents", dijkstra(g, b)[1] 

i expect answer be:

assuming start vertex b: shortest distances {'a': 4, 'c': 4, 'b': 0, 'e': 2, 'd': 1, 'g': 2, 'f': 4} parents {'a': 'd', 'c': 'g', 'b': none, 'e': 'd', 'd': 'b', 'g': 'd', 'f': 'e'} 

however, answer this:

assuming start vertex b: shortest distances {'a': 4, 'c': 4, 'b': 0, 'e': 2, 'd': 1, 'g': 2, 'f': 10} parents {'a': 'd', 'c': 'g', 'b': none, 'e': 'd', 'd': 'b', 'g': 'd', 'f': 'a'}. 

for node f, program gives incorrect answer. can please tell me why?

as others have pointed out, due not using understandable variable names, impossible debug code.

following wiki article dijkstra's algorithm, 1 can implement along these lines (and in million other manners):

nodes = ('a', 'b', 'c', 'd', 'e', 'f', 'g') distances = {     'b': {'a': 5, 'd': 1, 'g': 2},     'a': {'b': 5, 'd': 3, 'e': 12, 'f' :5},     'd': {'b': 1, 'g': 1, 'e': 1, 'a': 3},     'g': {'b': 2, 'd': 1, 'c': 2},     'c': {'g': 2, 'e': 1, 'f': 16},     'e': {'a': 12, 'd': 1, 'c': 1, 'f': 2},     'f': {'a': 5, 'e': 2, 'c': 16}}  unvisited = {node: none node in nodes} #using none +inf visited = {} current = 'b' currentdistance = 0 unvisited[current] = currentdistance  while true:     neighbour, distance in distances[current].items():         if neighbour not in unvisited: continue         newdistance = currentdistance + distance         if unvisited[neighbour] none or unvisited[neighbour] > newdistance:             unvisited[neighbour] = newdistance     visited[current] = currentdistance     del unvisited[current]     if not unvisited: break     candidates = [node node in unvisited.items() if node[1]]     current, currentdistance = sorted(candidates, key = lambda x: x[1])[0]  print(visited) 

this code more verbous necessary , hope comparing code mine might spot differences.

the result is:

{'e': 2, 'd': 1, 'g': 2, 'f': 4, 'a': 4, 'c': 3, 'b': 0}