Shortest Path – Dijkstra’s algorithm

Here are my whiteboard notes on how to implement the Dijkstra’s algorithm to find the shortest path of a graph:

Here is my simple c++ implementation of this:

The above is a very simple implementation of the algorithm. It is O(V²). We can optimise this to be something like O(E log V) by using a heap, map, or set data structure in the next_vertex_to_visit() function.

The above implementation is also not very object oriented. I felt that putting this functionality into classes would increase the complexity a bit and I wanted this to be as easy to understand as possible. If I was to implement this in production code then I would have a Graph class to encapsulate the logic.

This entry was posted in programming and tagged , . Bookmark the permalink.

Leave a Reply

Your e-mail address will not be published. Required fields are marked *