Dijkstra's Algorithm

Overview

Dijkstra's shortest path algorithm is used to find the minimum distance between nodes in a graph.
Notably, Dijkstra's algorithm does not work with negative edge weights. In the case of negative edges, you have to use a different algorithm, such as Bellman-Ford.

Steps

1. Create a visited array that has all nodes as unvisited
2. Set the minimum distances to every node to infinity
3. Create a priority queue of pair<distance, node> that sorts by smallest distance
4. Set the minimum distance to the start node to zero and push it into the priority queue
5. If the priority queue is empty, all nodes in the current connected component have been reached. Exit.
6. Pop a pair off the front of the priority queue. Optionally, return early if there is a specified end node and this is it.
7. If the node has already been visited, discard it and go back to step 5.
8. Set the minimum distance to that node equal to the current distance encoded in the pair object.
9. For every node that can be reached starting from the current node, push it into the queue (if it is not yet visited) with distance current plus the weight of the edge needed
10. Go to step 5

See the following site for more information: https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm