6
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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). $\endgroup$ – Ian Dec 2 '14 at 16:58
  • 3
    $\begingroup$ 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. $\endgroup$ – ml0105 Dec 2 '14 at 17:41
  • $\begingroup$ You are right. The queue wouldn't work. So how to approach the unweighted graph? $\endgroup$ – biryani Dec 3 '14 at 3:51
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – biryani Dec 3 '14 at 3:54
  • 1
    $\begingroup$ 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. $\endgroup$ – hardmath Dec 3 '14 at 4:04
  • 3
    $\begingroup$ 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. $\endgroup$ – Fizz Feb 27 '15 at 14:46
  • $\begingroup$ 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. $\endgroup$ – Fizz Feb 27 '15 at 14:56
  • $\begingroup$ @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. $\endgroup$ – hardmath Feb 27 '15 at 15:18
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.