Bug in Dijkstra pseudocode

[kjell.eikland@…]

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)

[Jeremiah Willcock]

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)?

[Marshall Clow]

I found it in libs/graph/doc/dijkstra_shortest_paths.html

Re-assigning this to Boost.Graph

[Jeremiah Willcock]

(In [85551]) Fixed pseudocode in documentation; fixes #9080