Dijkstra's algorithm without relaxation 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) &gt; 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))
I see you have tested the case when there is no path to the destination, but I'm not convinced that returning seemingly valid data in that case is a good idea. You can easily catch such case by adding an else clause to the main while loop. You will land there if the loop ends without break.
Disregarding the no path case you can simplify the second while loop to

path = []
while f in prev:
    path.append(f)
    f = prev[f]

The visited set is redundant because it is the same as the set of keys of prev, and v not in prev has similar performance to v not in visited.