Modify

Ticket #9080 (closed Bugs: fixed)

Opened 18 months ago

Last modified 18 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 18 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 18 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 18 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.