Dijkstra's algorithm

Dijkstra’s algorithm is an algorithm for the shortest path problem on a (non-negative) weighted, directed graph $G(V,E)$. It essentially generalises BFS to weighted graphs: like BFS, a wave emanates from the source, and a new wave emanates from a vertex once the wave arrives at it. This is provably able to always find the shortest path.

What’s the difference from BFS? BFS assumes each edge takes unit time to traverse. Dijkstra’s assumes that the travel time is given by the edge’s weights.

It takes a greedy approach for the single source shortest path problem in a fairly similar approach as Prim’s algorithm for the minimum spanning tree problem.

It has a time complexity of $\Theta ((|E|+|V|)\log |V|)$.

• As mentioned, Dijkstra’s is implemented with a priority queue. As a result of this, the time complexity of retrieving the next node is computed in $O(\log |V|)$ time. Since we call this for each next node, this process takes $O(|V|\log |V|)$.
• Because we also have to pre-populate the distance vector at the beginning of our algorithm, we add a complexity of $O(|E|)$.

Premise

Since the shortest path in a weighted graph might not have the fewest edges, a FIFO queue won’t suffice for choosing the next vertex to send out a wave from. Dijkstra’s stores the shortest travel time from the source at each node, then re-processes the node if the shortest travel time has dropped. This set $S$ holds vertices whose shortest path weights from the source have already been computed.

The algorithm repeatedly selects a vertex $u\in (V-S)$ with the minimum shortest-path estimate — these vertices are stored in a priority queue ordered by their edge weights/distances. Dijkstra’s always chooses the lightest vertex in $V-S$ to add to the priority queue $S$; it essentially uses a greedy approach.

Dijkstra’s improves on the Bellman-Ford algorithm by only processing each edge in the graph once. Note that unlike BF, the graph cannot have a negative weight. Because of the priority queue’s property, it means that edges with large positive weights balanced out by edges with large negative weights won’t be factored in.

Implementation

for (int i = 1; i <= n; i++) distance[i] = INT_MAX;
distance[x] = 0;
priority_queue<pair<int, int>> pq;
pq.push({0, x});
 
while (!pq.empty()) {
	int a = pq.top().second; pq.pop();
	if (processed[a]) continue;
	processed[a] = true;
	for (auto u: adj[a]) {
		int b = u.first, w = u.second;
		if (distance[a] + w < distance[b]) {
			distance[b] = distance[a] + w;
			pq.push({-distance[b], b});
		}
	}
}

Note that we use negative distances here, because by default the C++ STL priority queue finds maximum elements. We can alternatively specify a custom comparator function like std::greater<T>. Nevertheless, since the algorithm is agnostic to the ordering of the second element in the pair, we can define a simple lambda and continue with our day.

Quick links

• Bidirectional Dijkstra, by Matthew Towers

See also

• Bellman-Ford algorithm, for negative weights
• A-star algorithm, a heuristic approach for the shortest path problem