Graphs/Dijkstra

Notes

Dijkstra's algorithm is a weighted breadth-first search. it uses a greedy heuristic to select the next edge. It works by starting with an empty "cloud" of vertices, and adds vertices to the cloud in order of their distance from s.

The end result of Dijkstra's algorithm is the length of the shortest distance (weighted path) from the source vertex s to all other vertices v on the graph G.

The Central Idea: Edge Relaxation

The central idea in Dijkstra's algorithm is edge relaxation. To implement edge relaxation, we define a starting vertex s, and a map distance, which maps vertices to distances.

Specifically distance[v] stores the minimum distance so far from the source vertex s to some other vertex v. Initially, this quantity is infinity (i.e., initially we do not have any path connecting s to v, because we have not explored the graph), except for vertex s - distance[s] is initially 0.

We then define a set of vertices, which we will call the cloud, that consists of vertices that have been visited. This is initially the empty set.

Next, we add a new vertex u (not currently in the cloud) to the cloud. We select the next vertex u based on the node with the smallest value of distance[u] (using a Priority Queue).

Next, we loop over each vertex v adjacent to u, and update distance[v]. Note that this is updating the distance from s to the neighbors of u, not the distance from s to u. This is looking ahead to the next step, when we will look for the next vertex with the smallest distance from s. This step is where the actual relaxation procedure occurs - it takes an old estimate and checks if it can be improved to get closer to the true value.

We then move on to the next step: select the next vertex u (not in the cloud) based on the node with the smallest value of distance[u].