Site hosted by Angelfire.com: Build your free website today!

Text Box: 1   Initialization: 
2    N = {A} 
3    for all nodes v 
4      if v adjacent to A 
5        then Distance (v) = cost(A,v) 
6        else Distance (v) = infinity 
7 
8    Loop 
9     find w not in N such that Distance(w) is a minimum 
10    add w to N 
11    update Distance(v) for all v adjacent to w and not in N: 
12    Distance(v) = min( Distance(v), Distance(w) + cost(w,v) ) 
13    /* new distance to v is either old distance to v or known 
14     shortest path distance to w plus cost from w to v */ 
15   until all nodes in N 
  c(i, j) : link cost from node i to node j. 
  D(v) : current least cost of the path from the source node to destination v.
  p(v) : previous node (neighbor of v) along the current least cost path from the source to v
  N : set of nodes whose least-cost path from the source is definitively known.