Dijkstra's algorithm without relaxation

Question

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

Answer 1

The second loop. If you iterate through the list rather than index or slice it.

# Replace where path = [f]
def generator():
    node = f
    while node in prev:
        yield node
        node = prev[node]

return generator(), d

However you can say that the output is small enough for lst.append to not be too significant. And so I would use Janne Karila's second point.

---

Follow PEP8 more closely.

• Try to limit the amount of empty lines. However.
  • Module level functions and classes should have two blank lines above and below them.
  • Methods should have one blank line above and below them.
• Add spaces after commas. [(0, s, None)], 'w': [('t', 3)].

And while it doesn't tell you to not use single letters, don't. It's a pain to find out what p means, and you have to read the code multiple times to finally understand something you can know instantly with a good variable name.

---

can spot any problems?

dijkstra(g, 's', 'e') == (['e'], 7)

How did you get 'e', it's not in g, and how is it a distance 7? If you follow Janne Karila's answer this is solved.

Also, I thought Dijkstra's algorithm was meant to be undirected, not directional, travel. I can go from 's' to 'v' in a distance of 1. But I can't go from 'v' to 's'. I would change g so that it is a 2D dictionary. Then I would update the dictionary to allow bi-directional travel.

for node, routes in g.items():
    for child_node, distance in routes.items():
        # Use a try except for safety.
        g[child_node][node] = distance

You would also need to change for adj, adj_d in g[v]: to for adj, adj_d in g[v].items():. This is needed to do the 20-C problem. "You are given a weighted undirected graph"

The down side to this is it now uses \$O(2n)\$ memory. To 'fix' this you would need node and child_node to be the key, in such a way to allow you to get the key if they were both in either order.

---

correctness of the implementation

With the changes in this page it is fine.

• It works.
• It will allow undirected (bi-directional) travel.
• It won't say you can travel to undefined or untraversable nodes.

This is also ambiguous and opinion based. There are meany ways to implement binary trees. You can't ask 'what is the most correct implementation of binary trees?' They all make a binary tree.

This allows you to do Dijkstra's algorithm.

Answer 2

• 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.

Answer 3

A few details.

while len(h) > 0 can be rewritten while len(h) which can be rewritten while h.

---

Comparisons to singletons like None should always be done with is or is not , never the equality operators.

as per PEP8, the standard guide style.

so prev[f] != None should be prev[f] is not None.

---