Dijkstra's Algorithm

Complete the dijkstra function.

Inputs

• graph: An adjacency list (a dictionary of dictionaries)
• src: The key of the starting node
• dest: The key of the destination node

Outputs

• The shortest path from src to dest, represented as a list of node keys (i.e., a list of strings)

Algorithm

1. Create an empty unvisited set to keep track of the nodes that haven't yet been visited.
2. Create an empty predecessors dictionary to keep track of the path we're traversing.
3. Create an empty distances dictionary to keep track of the shortest known distance from src to each node.
4. Add each node to the unvisited set.
5. Set the distance to the src node to 0.
6. Set the distances to all other nodes to positive infinity.
7. While there are still nodes to visit:
   1. Get the unvisited node with the minimum distance from src using next_nearest_node.
   2. Mark that node as visited.
   3. If this next_nearest is the destination:
      1. We're done! Return the path to dest using get_path.
   4. Otherwise:
      1. For each unvisited neighbor of next_nearest:
         1. Get the currently known distance to next_nearest.
         2. Get the distance in the graph between next_nearest and the neighbor.
         3. Combine those 2 values to calculate the total distance from src to the neighbor.
         4. If the total distance to the neighbor is less than the distance we previously had stored for the neighbor in the distances dictionary:
            1. Update the distance we have stored for the neighbor.
            2. Update the predecessor of the neighbor to be next_nearest.