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