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?
 A: 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.
A: 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
