Dijkstra's algorithm in python

Question

I'm attempting to execute Dijikstra's algorithm in python with the help of arrays. Look at my implementation:

def extract(Q, w):

    m=0

    minimum=w[0]

    for i 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={}

    for i 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)

        for 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 the start vertex to be B:"

print "Shortest distances", dijkstra(G, B)[0]

print "Parents", dijkstra(G, B)[1]

I expect:

Assuming the start vertex to be 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'}

But what I get:

Assuming the start vertex to be 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'}.

It gives an incorrect answer for node F. Can anyone tell me why?

Answer 1

As others have brought up, because of not utilizing justifiable variable names, it is practically difficult to debug your code. 

Following the wiki article about Dijkstra's calculation, one can execute it thusly :

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 for node in nodes} #using None as +inf

visited = {}

current = 'B'

currentDistance = 0

unvisited[current] = currentDistance

while True:

    for neighbour, distance in distances[current].items():

        if neighbour not in unvisited: continue

        newDistance = currentDistance + distance

        if unvisited[neighbour] is None or unvisited[neighbour] > newDistance:

            unvisited[neighbour] = newDistance

    visited[current] = currentDistance

    del unvisited[current]

    if not unvisited: break

    candidates = [node for node in unvisited.items() if node[1]]

    current, currentDistance = sorted(candidates, key = lambda x: x[1])[0]

print(visited)

This code is more verbous than needed and I trust contrasting your code and mine you may detect a few contrasts.

result:

{'E': 2, 'D': 1, 'G': 2, 'F': 4, 'A': 4, 'C': 3, 'B': 0}

Interested to learn the concepts of python in detail? Come and join the python course to gain more knowledge in python

Watch this video tutorial on how to become a professional in python