id,summary,reporter,owner,description,type,status,milestone,component,version,severity,resolution,keywords,cc
9080,Bug in Dijkstra pseudocode,kjell.eikland@…,Andrew Sutton,"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)",Bugs,closed,To Be Determined,graph,Boost 1.54.0,Optimization,fixed,,