Opened 4 years ago
Closed 4 years ago
#9080 closed Bugs (fixed)
Bug in Dijkstra pseudocode
Reported by: | kjell.eikland@… | Owned by: | asutton |
---|---|---|---|
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 jewillco
comment:2 Changed 4 years ago by marshall
- Component changed from algorithm to graph
- Owner changed from marshall to asutton
I found it in libs/graph/doc/dijkstra_shortest_paths.html
Re-assigning this to Boost.Graph
comment:3 Changed 4 years ago by jewillco
- Resolution set to fixed
- Status changed from new to 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)?