# Is Dijkstra's algorithm optimal for unweighted graphs?

Dijkstra's algorithm is a very good approach to the shortest path problem. But is it optimal? Are there better algorithms for unweighted graphs?

• Wikipedia mentions several specialized implementations of Dijkstra's algorithm for graphs with bounded integer weights. Looking at the asymptotics they give (which depend on the bound on the weights), I would expect these implementations to be quite fast for graphs with constant weights (which is of course equivalent to unweighted graphs). – Ian Dec 2 '14 at 16:58
• Dijkstra's algorithm for unweighted graphs is simply a breadth-first traversal of the graph. The priority queue isn't helpful, as all edges have the same weight. – ml0105 Dec 2 '14 at 17:41
• You are right. The queue wouldn't work. So how to approach the unweighted graph? – biryani Dec 3 '14 at 3:51

Although simple to implement, Dijkstra's shortest-path algorithm is not optimal. A guaranteed linear time, linear space (in the number of edges) algorithm is referenced by the Wikipedia article Shortest path problem as:

As Mikkel Thorup points out in the abstract of the above:

Thus, any implementation of Dijkstra's algorithm sorts the vertices according to their distances from [single source] s. However, we do not know how to sort in linear time. Here, a deterministic linear time and linear space algorithm is presented for the undirected single source shortest paths problem with positive integer weights. The algorithm avoids the sorting bottleneck by building a hierarchical bucketing structure, identifying vertex pairs that may be visited in any order.

This effectively removes the dependency on number of vertices $V$ from $O(E + V\ln V)$ leaving only $O(E)$, where $E$ is the number of edges. Asano and Imai (2000) have an early but accessible account, Practical Efficiency of the Linear-Time Algorithm for the Single Source Shortest Path Problem. Slides from a 2009 talk by Nick Prühs are at Implementation of Thorup's Linear Time Algorithm for Undirected Single Source Shortest Paths With Positive Integer Weights.

We remark that linear-time is (quasi)optimal since in the worst case a shortest path consists of all the edges, and hence requires linear time to form the path.

• Thanks for the response! Will it work for unweighted cases? As i realised from the comments, Dijkstra's algorithm doesn't work for unweighted graphs. – biryani Dec 3 '14 at 3:54
• By unweighted graphs I assume you mean a constant weight of (say) 1 per edge. Otherwise it is unclear what a shortest path might mean. Dijkstra's algorithm works for positive real-valued weights, while Thorup's algorithm requires positive integer weights. Thus both will work for constant edge weight problems. – hardmath Dec 3 '14 at 4:04
• Alas, the practical efficiency of Thorup's algorithm (even with some modifications) is poor unless you use utterly huge problems. Only in mid-2014 was a Thorup-based algorithm shown to equal in performance (and slightly beat) a fairly trivial implementation of Dijkstra's, but the Thorup-based implementation used 75% more memory; see "Improvement of Thorup Shortest Path Algorithm by Reducing the Depth of A Component Tree" by Wei and Tanaka. – Fizz Feb 27 '15 at 14:46
• Eh, too late to edit that. They have a rather odd notion of "75% more" in that paper; looking at the raw data, they actually mean four times as much memory. That paper is also instructive as why don't want to bother (in practice) with Fibonacci heaps. – Fizz Feb 27 '15 at 14:56
• @RespawnedFluff: Thanks for the recent reference! It is quite typical that theoretically "optimal" algorithms are impractical at modest scales. The cases of deterministic primality testing and fast matrix multiplication are illustrations. – hardmath Feb 27 '15 at 15:18

For unweighted graphs you can use a simple Breadth-first Search to solve the problem in linear time.

While traversing the graph in a BFS manner, you can calculate and store the minimal distance from the source for each visited vertex. Particularly:

1. dist(Source) = 0
2. visiting a yet unvisited edge A->B implies that dist(B) = dist(A) + 1