Disjkstra's algorithm 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 vertexes 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.
The algorithm is due to the Dutch computer scientist Edsger Wybe Dijkstra.
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 using a heap as priority queue to implement the Extract-Min function.
Its time requirements are then Θ(m + n log n) (see Big O notation).
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 = S + u 4 if u == s 5 end 6 u = previous[u] 7 goto 3
Then read the sequence S in reverse order.
OSPF Open shortest path first is a well known real world implemenation used in internet routing.
References:
- Cormen, Leiserson, Rivest: Introduction to Algorithms