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.