Bare bone implementation of Dijkstra I am trying to implement Dijkstra without writing lot of code for the Graph class itself. I have implemented it from Wikipedia. However, I am not fond of the way I have handled the minimum distance calculation. I would like to have some improvement on that.

graph = {'s': {'v':1,'w':4 },
         'v': {'w':2,'t':6},
         'w': {'t':3},
         't': {'': None}
         }
def dj(graph, start):
    Q = []# queue to hold all the vertices
    dist = {} #dictionary to hold all the distance
    prev = {} #dictionary to hold all the previous node visited

    for key in graph.keys():
        dist[key] = 1000
        prev[key] = ""
        Q.append(key)


    dist[start] = 0

    #I had to have another distance data structure dst
    # to store all the distance covered
    # I am not fond of it
    dst = []

    while Q:
        # Here I get the minimum distance
        u = min(dist, key = dist.get)
        # remove the min one from Q
        Q.remove(u)
        for v in graph[u]:
            #I also want to improvise this condition block
            #It is because of 't': {'': None} 
            if graph[u][v] is None:
                continue
            alt = dist[u] + graph[u][v]
            if alt &lt; dist[v]:
                dist[v] = alt
                prev[v] = u
        #I have to discard the minimum key from dist dictionary
        d = (dist.pop(u))
        # I then have to append the discarded one to dst dictionary
        # Redundant work
        dst.append(d)

    return dst,prev

print(dj(graph,'s'))
for key in graph.keys():
        dist[key] = 1000



Why 1000? There are two values which are easy to defend here: positive infinity (which is the value that an algorithms textbook would use), or half the maximum value of the datatype (to avoid overflow when adding two weights). Even the second one of those requires a comment to justify it.


        prev[key] = ""



Why not just leave it undefined?


        Q.append(key)



What is the purpose of Q? It just seems to duplicate dist.keys().




    #I had to have another distance data structure dst
    # to store all the distance covered



Why? It's not used anywhere that I can see.




        # Here I get the minimum distance
        u = min(dist, key = dist.get)



Hopefully you can see that this is quite inefficient, and that's the motivation for using more sophisticated data structures.




            #I also want to improvise this condition block
            #It is because of 't': {'': None} 
            if graph[u][v] is None:
                continue



Why is it not just 't': {}?