Dijkstra's algorithm

Dijkstra’s algorithm is an algorithm for the shortest path problem on a (non-negative) weighted, directed graph $G(V,E)$. This is provably able to always find the shortest path. As a searching algorithm, it’s sometimes called uniform-cost search (UCS). It takes a greedy approach for the single source shortest path problem.

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. 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 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. Note that UCS doesn’t by default have a tiebreaking policy for edges with the same cost.

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.

Analysis

The first path found to a node is the cheapest path, i.e., it always gives a cost-optimal solution. The time complexity is $\mathcal{O}(b^{C\ast /ϵ+1})$, where the optimal cost is $C^{\ast }$ and actions cost at least $ϵ>0$. Then the effective depth is roughly $C^{\ast }/ϵ$.

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 also define a simple lambda and continue with our day.

Application

As a link-state routing algorithm

In computer networking, Dijkstra’s algorithm is known as a link-state routing algorithm. It is centralised, as in the network topology and link costs are known to all nodes. This is achieved by a link state broadcast. All nodes will have the same info. By computing the least cost paths from one node to all other nodes, we create a forwarding table for that node.

“Good”: least cost, fastest, least congested.

As with before, the algorithm complexity is $\mathcal{O}(n\log n)$. The broadcast algorithm also adds some complexity: $\mathcal{O}(n)$ link crossings to disseminate a broadcast message from one source with overall complexity $\mathcal{O}(n^2)$.

Note that when link costs depend on traffic volume, this means that route oscillations are possible, i.e., when the traffic changes, then the route paths change. This suggests that there’s no guarantee of termination in this circumstance, which is why later algorithms tended to not rely on traffic volume as a cost.

See also

• Bellman-Ford algorithm, for negative weights
• A-star algorithm, a heuristic approach for the shortest path problem
• Prim’s algorithm, a similar algorithm in approach for the minimum spanning tree problem