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?
Solution 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.
Solution 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:
- dist(Source) = 0
- visiting a yet unvisited edge A->B implies that dist(B) = dist(A) + 1
https://en.wikipedia.org/wiki/Breadth-first_search#Applications