Dijkstra's algorithm, named after its inventor the Dutch computer scientist Edsger Dijkstra, solves a shortest path problem for a directed and connected graph G(V,E) which has nonnegative (>=0) edge weights. The set V is the set of all vertices in the graph G. The set E is the set of ordered pairs which represent connected vertexes in the graph (if (u,v) belongs to E then vertexes u and v are connected).
Assume that the function w: V x V -> [0,oo) describes the cost w(x,y) of moving from vertex x to vertex y (non-negative cost). (We can define the cost to be infinite for pairs of vertices that are not connected by an edge.) For a given vertex s in V, the algorithm computes the shortest path (lowest total value of w) from s to any other vertex t.
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 vertexes
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)
Dijkstra's algorithm can be implemented efficiently by storing the graph in the form of adjacency lists and using a 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.
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.
OSPF Open shortest path first is a well known real world implemenation used in internet routing.
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.
References:
- Cormen, Leiserson, Rivest: Introduction to Algorithms