Dijkstras Algorithm

This solves the single-source shortest-paths problem on a weighted graph $G=(V,E,l)$ where $l(u,v)\ge 0$ for all $(u,v)\in E$.

The idea

1. Maintain an estimate dist(v) of distance from s to v
2. Ensure this estimate is never smaller than the true distance
3. Keep track of set H of vertices whose dist value may not yet be correct
4. Then select. the vertex v in H that has the smallest distance
5. Remove v from H and recalculate the dist estimate to all vertices u connected to v

To write precisely, we need a data structure for storing vertices and their current distance estimates.

We can use a Priority Queue.

procedure dijkstra(G,l,s)  
Input: A graph G = (V, E) (directed or undirected); non-negative edge lengths l(u, v) for each (u, v) in E; and a start vertex s in V  
Output: For all u reachable from s, dist(u) is set to the distance from s to u
	for all u in V:
		dist(u) = inf
		prev(u) = nil
	dist(s) = 0
	H = makequeue(V, dist)
	while H is not empty:
		u = deletemin(H)
		for all edges (u, v) in E:
			if dist(v) >= dist(u) + l(u, v):
				dist(v) = dist(u) + l(u, v)
				prev(v) = u
				decreasekey(H, v, dist(v))

• Here, prev gives the identity of the vertex immediately before v on the shortest path from s to v and can follow prev pointers to reconstruct the shortest path from s to any v. We can also prove the correctness of this through Proof by Induction.

Runtime

This depends on how the priority queue is implemented. Using an array, this typically runs in $O(V^2)$ time and $O((V+E)\log V)$ using a tree based heap.

Negative Weights

Dijkstra’s doesn’t work by default with negative weights. We use Bellman-Ford Algorithm instead.