My journey on Implementing Dijkstra’s algorithm

featured
April 20, 2017
💫 Originally posted here. Broken? Let me know ~

Featured Image of Edsger Wybe Dijkstra from Wikipedia, used under CC BY 3.0.

I’ve spent about 3 days trying to implement Dijkstra’s algorithm after watching a YouTube video.

I’ve implemented three times (once a day) but on the 3rd day, I finally succeeded.

This entry is neither going to be about what Dijkstra’s algorithm is nor how the implementation works. I will just talk about steps I took to implement it and post the full source link on the bottom.

Here is how I spent each day.

Day 1

I used pseudocode on Wikipedia page and some other algorithms I found elsewhere. I failed splendidly because I didn’t understand how the algorithm worked behind the scenes.

Here is the failed implementation.

It’s basically a hodgepodge of a mess (the last implementation looks ugly as well by the way) and doesn’t work at all. I knew that I was lacking knowledge on how the algorithm worked.

Day 2

After understanding how the algorithm works was important, I found a great video on YouTube by Sesh Venugopal and watched it before implementing another version.

The video explains visually how the algorithm works. The video also explains its own version of the algorithm. I decided to use the algorithm in the video to implement for the second time.

But I failed beautifully again because I couldn’t get the Wikipedia and other versions of algorithms out of my head.

Here is the 2nd failed attempt.

Day 3

I read Wikipedia pseudocode again. I was armed with the knowledge of how the algorithm worked after watching the video, I decided to read Wikipedia algorithm and give it one more try.

After some struggle here and there, I’ve finally completed the implementation.

It’s kind of funny that, after watching it work, I felt ecstatic and felt a jolt in my head. “Ah, this is why I decided to learn to program” was my first thought after realizing what happened.

Here is the 3rd working implementation.

It’s by no means production ready, so copy/paste at your own risk. I’d never release this to production without heavy testing and refactoring first.

Here is the full source (including Main, Node, Graph implementations) on GitHub.

Also, check out Max Burstein‘s C# implementation on GitHub. I found Max’s implementation much cleaner and easier to understand.

Conclusion

The journey was tough but was quite worth it. It has given me more confidence as a developer.