Shortest Path

Find Path

We slightly modify the general graph search problem by adding the goal:

Goal: Identify a path from $s$ to each (reachable) vertex in $G$. 

We modify the BFS algorithm pseudocode

// Pre: "s" is the source vertex 
// Pre: pre will store the previous information
pre = {}
explored = {} 
explored[s] = true 
pre(s) = null
queue.enqueue(s) 
while (!queue.empty())
	v = queue.dequeue()
	for (w in adjacency[v]) 
		if (!explored[w]) 
			explored[w] = true 
			queue.enqueue(w)
			pre[w] = v

• we now store the previous information.

Find Distance

Modfiy the general graph search problem by adding a new goal: Goal: Find the distance of each (reachable) vertex in $G$ to $s$, where "distance" is defined as the length of a path from $s$ to the other vertex.

We modify the BFS algorithm pseudocode

// Pre: "s" is the source vertex 
// Pre: distance will store the distance from the first node
distance = {}
explored = {} 
explored[s] = true 
distance(s) = 0
queue.enqueue(s) 
while (!queue.empty())
	v = queue.dequeue()
	for (w in adjacency[v]) 
		if (!explored[w]) 
			explored[w] = true 
			queue.enqueue(w)
			distance[w] = distance[v]+1

Find Shortest Path

The shortest path problem Note we are considering the length of a path here. In other words, "shortest path" means "shortest length."

BFS finds the shortest path because because BFS will look at all the vertices 1 edge away first, then 2 edges away.

Weighted Graph

A weighted graph is a labeled graph where edge labels are numbers.

• BFS will no longer find the shortest path because it will only find the shortest length. It will not update this 'shortest' path when it finds a second cheaper path because it will already be marked as explored.

Dijkstra's Algorithm

It works by exploring the neighbors of the next vertex with the smallest distance to the source vertex. This is called the shortest path first (SPF) algoirhtm.

• If B is on the shortest path from A to D, then the subpath from B to D is also the shortest path between vertices B and D.

Pseudocode:

for each vertex v // O(n)
	distance[v] = Infinity
	previous[v] = null
	explored[v] = false;
	
distance[s] = 0 // s is the source
repeat N times // O(n)
	let v be unexplored vertex with smallest distance // O(?)
	explored[v] = true
	for every u: unexplored neighbor(v) // O(degree(V))
		d = distance[v] + weight [v,u] 
		if d < distance[u]
			distance[u] = d
			previous[u] = v

For the line with O(?), how do you extract the vertex with the smallest distance?

• With a priority queue! However, the distance of each vertex will change, so you need to find a way to consistently update which would be the min.