Snakes and Active Contours - Bezier and Splines in Image Processing and Machine Vision - page 193

function Dijkstra(G, w, s) // G = graph

// w = costs
// s = start node

for each vertex v in V[G] // Initializations

d[v] := infinity
previous[v] := undefined
d[s] := 0
S := empty set // S = known nodes

Q := V[G] // Q = trial nodes

while Q is not an empty set // The algorithm

u := Extract_Min(Q)
S := S union {u}
for each edge (u,v) outgoing from u
if d[u] + w(u,v) < d[v]
d[v] := d[u] + w(u,v)
previous[v] := u

Fig. 9.8. Pseudocode for Dijkstra's Algorithm for finding the shortest path on a
graph or network.

Fig. 9.9. Air transportation network converted to a trellis.