I'm trying to implement Dijkstra's algorithm in Python, but the issue is that Python doesn't have support for key-based heaps out of the box, so applying relaxation step of the classical algorithm presented in CLRS becomes cumbersome.
My idea is to keep maintaining current total distance and then pushing frontier nodes with it. It seems to work both with the basic examples I can think of and pass codeforce's 20-C: Dijkstra?, which literally just tests algorithm implementation without need for modifications.
However, I don't have enough experience to reason about correctness and I can't figure out if my implementation is actually correct. Please take a look at my implementation and see if you can spot any problems?
from heapq import heappop, heappush
def dijkstra(g, s, f):
h = [(0,s,None)]
visited, prev = set(), {}
while len(h) > 0:
d,v,p = heappop(h)
if v not in visited:
visited.add(v)
prev[v] = p
if v == f:
break
for adj, adj_d in g[v]:
if adj not in visited:
heappush(h, (adj_d + d, adj, v))
path = [f]
while f in prev and prev[f] != None:
f = prev[f]
path.append(f)
return path[::-1], d
if __name__ == '__main__':
g = {'s':[('v',1),('w',4)],'v':[('w',2),('t',6)],'w':[('t',3)],'t':[]}
print(dijkstra(g, 's', 't') == (['s', 'v', 'w', 't'], 6))
print(dijkstra(g, 's', 'e') == (['e'], 7))