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