I have been working through *Algorithm’s Design and Analysis I* by Stanford, via Coursera. It is quite heavily theoretical, which I guess you would assume from the title but along with the final exam and weekly tests, there have been weekly programming challenges which have been rewarding to do. Like the *Introduction to Databases* course this has been really fast paced and quite demanding, but well worth the effort. Nearly over now, all the tests and the exam complete, I have one more programming challenge to do.

This evening, I finished my implementation of Dijkstra’s shortest path algorithm. I really enjoyed this programming challenge. The theory behind Dijkstra’s algorithm is perhaps a little bland, but I found the algorithm itself really fascinating. There is something ‘complete’ about this algorithm, it seems incredibly sound and well-suited about it.

I haven’t posted about any of the previous challenges, so why this one? It is timely to put Dijkstra’s algorithm towards the end of an algorithm / data structure course, because there are good ways and better ways to implement it. Below is my current implementation in Python, I like it, but there are places to improve and it is these improvements that I want to track in this post.

def dijkstra(graph):
X = set()
path_lengths = defaultdict(int)
X.add(1)
path_lengths[1] = 0
while not X == graph.keys():
step, score = None, float('inf')
for node in X:
for child, cost in children(graph[node], X):
price = path_lengths[node] + cost
if price < score:
step, score = child, price
path_lengths[step] = score
X.add(step)
return path_lengths
def children(p, x):
return ((child, cost) for (child, cost) in p if not child in x)

**In its favour:**

- It is short
- It is pretty clean
- It is reasonably fast (on the challenge graph it completed in 0.22 seconds)

**What I would like to improve:**

- Rename `X` – this isn’t brilliant, it certainly isn’t descriptive
- It needs some comments. It is pretty clear, but comments would be nice
- Implement with a
**HEAP**. The entire *for node in X…* loop is simply to find the minimum length path from outgoing edges. This screams out **HEAP!** – which hopefully will maintain the performance even for large graphs.

### Like this:

Like Loading...

*Related*