Modify

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

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

  • 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

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

Add Comment

Modify Ticket

Change Properties
Set your email in Preferences
Action
as closed The owner will remain asutton.
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.