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.
This archive was generated by hypermail 2.1.7 : 2017-02-16 18:50:14 UTC