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