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 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 constructing a subgraph S of such that the distance of any vertex v' (in S) from s is known to be a minimum within G. Initially S is simply the single vertex s, and the distance of s from itself is known to be zero. Edges are added to S at each stage by (a) identifying all the edges ei = (vi1,vi2) in G-S such that vi1 is in S and vi2 is in G, and then (b) choosing the edge ej = (vj1,vj2) in G-S which gives the minimum distance of its vertex vj2 (in G) from s from all edges ei. The algorithm terminates either when S becomes a spanning tree of G, or when all the vertices of interest are within S.
The procedure for adding an edge ej to S maintains the property that the distances of all the vertices within S from s are known to be minimum.
Pseudocode
A few subroutines for use with Dijkstra's algorithm:
Initialize-Single-Source(G,s)
1 for each vertex v in V[G] 2 do d[v] := infinite 3 previous[v] := 0 4 d[s] := 0
Relax(u,v,w)
1 if d[v] > d[u] + w(u,v) 2 then d[v] := d[u] + w(u,v) 3 previous[v] := u
v = Extract-Min(Q) searches for the vertex v in the vertex set Q that has the least d[v] value. That vertex is removed from the set Q and then returned.
The algorithm:
Dijkstra(G,w,s)
1 Initialize-Single-Source(G,s)
2 S := empty set
3 Q := set of all vertices
4 while Q is not an empty set
5 do u := Extract-Min(Q)
6 S := S union {u}
7 for each vertex v which is a neighbour of u
8 do Relax(u,v,w)
If we are only interested in a shortest path between vertexes s and t, we can terminate the search at line 5 if u == t.
Now we can read the shortest path from s to t by iteration:
1 S = empty sequence 2 u := t 3 S = u + S /* 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.
Related problems and algorithms
OSPF (Open shortest path first) is a well known real world implementation used in internet routing.
Unlike Dijsktra's algorithm, Bellman-Ford’s algorithm can be used on the graphs with negative edge weights, as long as the graph contains no negative cycle reachable from the source vertex s.
A related problem is the traveling salesman problem, which is the problem of finding the shortest path that goes through every vertex exactly once, and returns to the start. That problem is NP-hard, so it can't be solved by Dijkstra's algorithm, nor by any other known, polynomial-time algorithm.
See Also
References
- Cormen, T. H.; Leiserson C. E.; & Rivest R. L. (1990) Introduction to Algorithms. MIT Press. ISBN 0-262-03141-8