[Boost-bugs] [Boost C++ Libraries] #9080: Bug in Dijkstra pseudocode

Subject: [Boost-bugs] [Boost C++ Libraries] #9080: Bug in Dijkstra pseudocode
From: Boost C++ Libraries (noreply_at_[hidden])
Date: 2013-09-03 16:54:12

#9080: Bug in Dijkstra pseudocode
------------------------------+--------------------------
 Reporter:  kjell.eikland@…   |      Owner:  marshall
     Type:  Bugs              |     Status:  new
Milestone:  To Be Determined  |  Component:  algorithm
  Version:  Boost 1.54.0      |   Severity:  Optimization
 Keywords:                    |
------------------------------+--------------------------
 The Boost library uses deferred heap entry for the entering variable.  In
 the pseudocode at the bottom here INSERT is incorrectly placed and would
 nominally lead to the entering variable being defined twice. The correct
 pseudocode is given below

 Kjell


 DIJKSTRA(G, s, w)
   d[s] := 0
   INSERT(Q, s)
   while (Q != Ø)
     u := EXTRACT-MIN(Q)
     for each vertex v in Adj[u]
       if (w(u,v) + d[u] < d[v])
         d[v] := w(u,v) + d[u]
         p[v] := u
         if (d[v] was originally infinity)
            INSERT(Q, v)
          else
            DECREASE-KEY(Q, v)
       else
         ...
     end for
   end while
   return (d, p)

 -----------------------

 DIJKSTRA(G, s, w)
   d[s] := 0
   INSERT(Q, s)
   while (Q != Ø)
     u := EXTRACT-MIN(Q)
     for each vertex v in Adj[u]
       if (w(u,v) + d[u] < d[v])
         d[v] := w(u,v) + d[u]
         p[v] := u
         DECREASE-KEY(Q, v)
       else
         ...
       if (d[v] was originally infinity)
         INSERT(Q, v)
     end for
   end while
   return (d, p)

-- 
Ticket URL: <https://svn.boost.org/trac/boost/ticket/9080>
Boost C++ Libraries <http://www.boost.org/>
Boost provides free peer-reviewed portable C++ source libraries.