Finding the Shortest Path

I’ve known about Dijkstra’s algorithm for a long time, but never took the time to review it and then try to implement it on my own to prove whether I really understood the concept. Until today. I stumbled upon Eoin Bailey’s explanation of Dijkstra’s algorithm, and found it to be quite helpful.

As I was reviewing the algorithm, it struck me that I could probably use a min heap in order to keep track of which node to visit next. Fortunately, a few months ago I wrote a series of C# extension methods to “heapify” a list in exactly the same way that heapq does for Python. It was incomplete (and still is), but enough of the methods were in place that I could make use of it.

I ran into a few bugs, particularly when a longer path was calculated. It turns out the incomplete min heap had a few bugs in it. Once those were ironed out, the algorithm implementation seemed to work flawlessly.

My Dijkstra’s algorithm implementation is contained in my slowly growing DataStructures project on GitHub, if you’re interested in taking a peek.

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

%d bloggers like this: