Meeting Dijkstra

I spent the last couple of weekends implementing Dijkstra's Shortest Path algorithm in Java. DSP is a fairly straight forward algorithm built on simple steps. Nevertheless I found it trickier than expected to convert it to code, my "work experience" and familiarity with Java notwithstanding. In the end I was able to work out a reasonable implementation after going through a few iterations.

I realised that in spite of working daily on a large body of code I was out of shape programming wise when it came to implementing algorithms. Part of the reason is my own average skill level; part of it is how rarely I tangle with algorithms at work. I suspect that this is the case with most programming jobs in town. There are other reasons as well not least of them being that algorithms require considerable thought to translate to code.

One of the interesting problems I faced had concerned representing the domain in code. For instance DSP works on Graphs made up of Vertices connected by Edges. It was fun to work out how to represent a Graph programmatically. In the end I chose method #1 suggested by Cormen et al., namely maintain Adjacency Lists.

Overall I found getting back in touch with the fundamentals an enjoyable experience. I plan to take this exercise further over the course of the next six months by working through Introduction to Algorithms. In the end I hope to emerge with a better understanding of the fundamentals.