Modify

Opened 4 years ago

Closed 4 years ago

#9080 closed Bugs (fixed)

Bug in Dijkstra pseudocode

Reported by: kjell.eikland@… 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 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)?

comment:2 Changed 4 years ago by Marshall Clow

Component: algorithmgraph
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 Jeremiah Willcock

Resolution: fixed
Status: newclosed

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

Modify Ticket

Change Properties
Set your email in Preferences
Action
as closed The owner will remain Andrew Sutton.
The resolution will be deleted.

Add Comment


E-mail address and name can be saved in the Preferences.

 
Note: See TracTickets for help on using tickets.