[prev] [index] [next]

Dijkstra's Algorithm

One approach to solving single-source shortest path ...

Data: G, s, dist[], pred[], and ...

  • vSet: set of vertices whose shortest path (so far) from s is known
Method: 

initialise vSet to {s} (source vertex)
initialise dist[] to all ∞, except dist[s]=0
while (any edges left to consider) {
   choose an edge e where
      e connects v in vSet
      and e is the minimum weight such edge
   relax along e, add w to vSet
}