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

• Please do not update the code in your question to incorporate feedback from answers, doing so goes against the Question + Answer style of Code Review. This is not a forum where you should keep the most updated version in your question. Please see what you may and may not do after receiving answers.
– Mast
Jan 23, 2018 at 18:21
• Sorry - no problem . Jan 23, 2018 at 18:22
• Your implementation is not correct as it throws on larger graphs. I am not answering, but you could take a look at this implementation. It's a point-to-point version, but may be easily modified to do the single-source shortest paths. Jan 23, 2018 at 19:57

## 1 Answer

    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': {}?

• u = min(dist, key = dist.get) - should I use a heap? Jan 23, 2018 at 18:27
• More precisely, you're using a rather inefficient heap, and you should think about using a more efficient one. If you're doing this as a learning exercise you could work your way through simple binary heap, Fibonacci heap, and maybe something really exotic. Jan 23, 2018 at 19:34