Holiday Projects / python

Dijkstra’s Shortest Path Algortihm

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s