Dijkstra's algorithm

Disjkstra's algorithm solves a shortest-paths problem for a directed and connected graph G(V,E) which has nonnegative (>=0) weights. Set V is the set of all vertexes in graph G. 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 function w:(x,y)->[0,oo) is the cost of moving from vertex x to vertex y (non-negative cost). (we can define the cost to be infinite for pairs that are not connected)

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)

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.

Dijkstra's algorithm can be implemented efficiently by using heap as priority queue to implement the Extract-Min function.

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.

For reference, see any decent basic algorithm book. Dijkstra algorithm was presented like this in 'Introduction to Algorithms' by Cormen, Leiserson & Rivest.

This is related to 'Shortest path problem' entry. Someone first check this, and then link that article here.