Is Dijkstra's algorithm optimal for unweighted graphs?

Question

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

Answer 1

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:

Thorup, Mikkel (1999) "Undirected single-source shortest paths with positive integer weights in linear time". Journal of the ACM 46 (3): p. 362–394

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.

Answer 2

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

https://en.wikipedia.org/wiki/Breadth-first_search#Applications