next up previous
Next: October 18 Up: October 16 Previous: Shortest distance


Dijkstra's algorithm

      DIJKSTRA ( V, E, s )
         for each v in V
            d[v] := oo;   ("infinity")
            pred[v] := NULL;
         end for
         d[s] := 0;
         S := {};
         V' := V;
         while ( V' is not empty ) do
            find a vertex u in V' such that d[u] is minimum;
            V' := V' - {u};
            S := S U {u};
            for each edge e = (u,v) in E
               if ( v is not in S ) and ( d[v] > d[u] + w(u,v) ) then
                  d[v] := d[u] + w(u,v);
                  pred[v] := u;
               end if
            end for
         end while
      END
At each iteration of the while loop we add a vertex $ u$ to the solution set $ S$, and never change its distance ($ d[u]$) again. You should worry that, perhaps, there is some shorter distance from $ s$ to $ u$ using some vertex that hasn't yet been added to $ S$. Convince yourself that this can't happen.



Danny Heap 2002-12-16