Boost C++ Libraries: Ticket #9080: Bug in Dijkstra pseudocode https://svn.boost.org/trac10/ticket/9080 <p> 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 </p> <p> Kjell </p> <p> DIJKSTRA(G, s, w) </p> <blockquote> <p> d[s] := 0 INSERT(Q, s) while (Q != Ø) </p> <blockquote> <p> u := EXTRACT-MIN(Q) for each vertex v in Adj[u] </p> <blockquote> <p> if (w(u,v) + d[u] &lt; d[v]) </p> <blockquote> <p> d[v] := w(u,v) + d[u] p[v] := u if (d[v] was originally infinity) </p> <blockquote> <p> INSERT(Q, v) </p> </blockquote> <p> else </p> <blockquote> <p> DECREASE-KEY(Q, v) </p> </blockquote> </blockquote> <p> else </p> <blockquote> <blockquote> <blockquote> <p> ... </p> </blockquote> </blockquote> </blockquote> </blockquote> <p> end for </p> </blockquote> <p> end while return (d, p) </p> </blockquote> <hr /> <p> DIJKSTRA(G, s, w) </p> <blockquote> <p> d[s] := 0 INSERT(Q, s) while (Q != Ø) </p> <blockquote> <p> u := EXTRACT-MIN(Q) for each vertex v in Adj[u] </p> <blockquote> <p> if (w(u,v) + d[u] &lt; d[v]) </p> <blockquote> <p> d[v] := w(u,v) + d[u] p[v] := u DECREASE-KEY(Q, v) </p> </blockquote> <p> else </p> <blockquote> <blockquote> <p> ... </p> </blockquote> </blockquote> <p> if (d[v] was originally infinity) </p> <blockquote> <p> INSERT(Q, v) </p> </blockquote> </blockquote> <p> end for </p> </blockquote> <p> end while return (d, p) </p> </blockquote> en-us Boost C++ Libraries /htdocs/site/boost.png https://svn.boost.org/trac10/ticket/9080 Trac 1.4.3 Jeremiah Willcock Tue, 03 Sep 2013 17:54:31 GMT <link>https://svn.boost.org/trac10/ticket/9080#comment:1 </link> <guid isPermaLink="false">https://svn.boost.org/trac10/ticket/9080#comment:1</guid> <description> <p> Which file is this in? Are you sure it isn't from Boost.Graph (in which case, it needs to be marked with a different component)? </p> </description> <category>Ticket</category> </item> <item> <dc:creator>Marshall Clow</dc:creator> <pubDate>Tue, 03 Sep 2013 18:02:25 GMT</pubDate> <title>owner, component changed https://svn.boost.org/trac10/ticket/9080#comment:2 https://svn.boost.org/trac10/ticket/9080#comment:2 <ul> <li><strong>owner</strong> changed from <span class="trac-author">Marshall Clow</span> to <span class="trac-author">Andrew Sutton</span> </li> <li><strong>component</strong> <span class="trac-field-old">algorithm</span> → <span class="trac-field-new">graph</span> </li> </ul> <p> I found it in libs/graph/doc/dijkstra_shortest_paths.html </p> <p> Re-assigning this to Boost.Graph </p> Ticket Jeremiah Willcock Tue, 03 Sep 2013 18:13:01 GMT status changed; resolution set https://svn.boost.org/trac10/ticket/9080#comment:3 https://svn.boost.org/trac10/ticket/9080#comment:3 <ul> <li><strong>status</strong> <span class="trac-field-old">new</span> → <span class="trac-field-new">closed</span> </li> <li><strong>resolution</strong> → <span class="trac-field-new">fixed</span> </li> </ul> <p> (In <a class="changeset" href="https://svn.boost.org/trac10/changeset/85551" title="Fixed pseudocode in documentation; fixes #9080">[85551]</a>) Fixed pseudocode in documentation; fixes <a class="closed ticket" href="https://svn.boost.org/trac10/ticket/9080" title="#9080: Bugs: Bug in Dijkstra pseudocode (closed: fixed)">#9080</a> </p> Ticket