Dijkstra's algorithm

Dijkstra's algorithm, named after its inventor the Dutch computer scientist Edsger Dijkstra, solves the shortest path problem for a directed graph with nonnegative edge weights. For example, if the vertices of the graph represent cities and edge weights represent driving distances between pairs of cities connected by a direct road, Dijkstra's algorithm can be used to find the shortest route between two cities.

The input of the algorithm consist of a weighted directed graph G and a source vertex s in G. We will denote V the set of all |vertices in the graph G. Each edge of the graph is an ordered pair of vertices (u,v) representing a connection from vertex u to vertex v. Set of all edges is denoted E. Weights of edges are given by a weight function w: E -> [0, ∞]; therefore w(u,v) is the non-negative cost of moving from vertex u to vertex v. The cost of an edge can be thought of as (a generalisation of) the distance between those two vertices.

The cost of a path between two vertices is the sum of costs of the edges in that path. For a given pair of vertices s and t in V, the algorithm finds the path from s to t with lowest cost (i.e. the shortest path). It can also be used for finding costs of shortest paths from a single vertex s to all other vertices in the graph.

Description of the algorithm

The algorithm works by keeping for each vertex v the cost d[v] of the shortest path found so far. Initially, this value is 0 for the source vertex s and infinity for all other vertices, representing the fact that we do not know any path leading to those vertices. When the algorithm finishes, d[v] will be the cost of the shortest path from s to v or infinity, if no such path exists.

The algorithm also maintains two sets of vertices S and Q. Set S contains all vertices for which we know that the value d[v] is already the cost of the shortest path and set Q contains all other vertices. Set S starts empty, and in each step one vertex is moved from Q to S. This vertex chosen as the vertex with lowest value of d[u]. When a vertex u is moved to S, the algorithm checks for every outgoing edge (u,v), whether it cannot be used to create a path with lower cost than the cost currently stored in d[v].

Pseudocode

In the following algorithm, u := Extract-Min(Q) searches for the vertex u in the vertex set Q that has the least d[u] value. That vertex is removed from the set Q and then returned.

Dijkstra(G,w,s)

1  for each vertex v in V[G]
2     do d[v] = infinity
3        previous[v] = undefined
4  d[s] = 0
5  S = empty set
6  Q = set of all vertices
7  while Q is not an empty set
8        do u = Extract-Min(Q)
9           S = S union {u}
10          for each vertex v which is a neighbour of u
11              do if d[v] > d[u] + w(u,v)
12                          then d[v] = d[u] + w(u,v)
13                                 previous[v] = u

If we are only interested in a shortest path between vertices s and t, we can terminate the search at line 8 if u == t.

Now we can read the shortest path from s to t by iteration:

1 S = empty sequence
2 u = t
3 insert u to the beginning of S
4 if u == s
5    end
6 u = previous[u]
7 goto 3

Now sequence S has the shortest path from s to t.

Running time

Dijkstra's algorithm can be implemented efficiently by storing the graph in the form of adjacency lists and using a Fibonacci heap as priority queue to implement the Extract-Min function. If the graph has m edges and n vertices, then the algorithm's time requirements are Θ(m + n log n) (see Big O notation), assuming that comparisons of edge weights take constant time.

References

Cormen, T. H.; Leiserson C. E.; & Rivest R. L. (1990) Introduction to Algorithms. MIT Press. ISBN 0-262-03141-8

External links

Animation of Dijkstra's algorithm