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