Graph Traversal + Dijkstra's Algorithm
4Today we went over a pattern that comes up a lot when doing a graph traversal: keep two data structures, one holding all the vertices we've processed, and one containing the vertices we want to process next.
We do this in a loop:
1) Move a vertex off the "to process" list and onto the "processed" list.
2) Add all of its kids that have not been processed yet to the "to process" list
3) Repeat until the "to process" list is empty.
I say list, but the "processed" list is often a hash table, and the "to process" list is often a priority queue (i.e. a heap).
We then showed how this pattern can be used to compute the shortest paths from one starting vertex to all other vertices connected to it on a weighted (i.e. the edges have values) graph. You simply have the "to process" list sorted by the total distance the node is away from the starting node, and all the rest of the code is the same.