Dijkstra's Algorithm

• one of the first label-setting algorithms developed by Dijkstra

• a general method to solve the single-source shortest-path problem

• useful for directed and positive weighted graphs

• algorithm proceeds as following in each stage:

  1. mark each vertex as either known or unknown
  2. tentative distance dv, from a source to a vertex, is kept
  3. known vertices is determined by the distance that turns out to be the shortest path length
  4. select a vertex v, which has the smallest path dv among all the unknown vertices
  5. declare the shortest path from source to vertex to known
  6. the remainder of a stage consists of updating the values of adjacent distance dw
  7. set dw = dv + c(v,w) where c= cost of adjacent distance dw from vertex v, only if dw is improved

   

click here to link for JAVA applet examples

packet format >>