Modify

Ticket #9080 (closed Bugs: fixed)

Opened 8 months ago

Last modified 8 months ago

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

Change History

comment:1 Changed 8 months ago by jewillco

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 8 months ago by marshall

  • Owner changed from marshall to asutton
  • Component changed from algorithm to graph

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

Re-assigning this to Boost.Graph

comment:3 Changed 8 months ago by jewillco

  • Status changed from new to closed
  • Resolution set to fixed

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

View

Add a comment

Modify Ticket

Change Properties
<Author field>
Action
as closed
The resolution will be deleted. Next status will be 'reopened'
Author


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

 
Note: See TracTickets for help on using tickets.