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].

Pseudocode

Edge Relaxation Pseudocode

Pseudocode for edge relaxation is a search for shorter distances. It compares the current shortest distance to the shortest distance based on the "hop" from a current vertex (via a traversal) to the vertex in question:

// This procedure occurs during a weighted breadth-first search starting at a source vertex s
// It updates the shortest distances from the source vertex s to the vertex in question v
if distance[u] + w(u,v) < distance[v]:
    distance[v] = distance[u] + w(u,v)

By performing this edge relaxation procedure during a weighted breadth-first search, we can assemble a map/dictionary "distance" that contains the shortest path from a source node s to a given node v.

Dijkstras Agorithm Psuedocode

// Assembles a map "distance" containing the shortest path 
// from a source vertex s to every other vertex
// in a graph g
def shortest_path(g,s):
	initialize distance map
	distance[:] = infinity
	distance[s] = 0
	initialize a priority queue pq containing all vertices of g

	while pq is not empty:

		// pull new vertex u into cloud
		// the first time thru, everything is infinity except s
		// so we are considering s
		u = pq.remove_min()

		// update values of distance[neighbors of s]
		for each vertex v adjacent to u:
			if v in pq:
				// edge relaxation - 
				// this ensures we update info at each step,
				// and that we are always making the best possible choice
				if distance[u] + w(u,v) < distance[v]:
					distance[v] = distance[u] + w(u,v)
					update pq[v] with new value of distance[v]