Opened 4 years ago
Closed 4 years ago
#9080 closed Bugs (fixed)
Bug in Dijkstra pseudocode
Reported by: | Owned by: | Andrew Sutton | |
---|---|---|---|
Milestone: | To Be Determined | Component: | graph |
Version: | Boost 1.54.0 | Severity: | Optimization |
Keywords: | Cc: |
Description
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)
Attachments (0)
Change History (3)
comment:1 Changed 4 years ago by
comment:2 Changed 4 years ago by
Component: | algorithm → graph |
---|---|
Owner: | changed from Marshall Clow to Andrew Sutton |
I found it in libs/graph/doc/dijkstra_shortest_paths.html
Re-assigning this to Boost.Graph
comment:3 Changed 4 years ago by
Resolution: | → fixed |
---|---|
Status: | new → closed |
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)?