Modify

Opened 5 years ago

Closed 5 years ago

Last modified 5 years ago

#7398 closed Bugs (fixed)

edge weights equal to distance_inf not correctly supported in dijkstra

Reported by: Alex Hagen-Zanker <ahh34@…> Owned by: Jeremiah Willcock
Milestone: To Be Determined Component: graph
Version: Boost 1.52.0 Severity: Problem
Keywords: dijkstra, relax Cc:

Description

The way that the relax() function works in relax.hpp is such that an edge_weight of distance_inf will not be consider for a shortest path.

The can lead to the false conclusion that vertices connected only through infinite cost edge are not connected at all.

This bug is related to #7387 and #7226. The patch of #7387 also solves this problem.

I am attaching an example with failing assertion.

Attachments (1)

main.cpp (1.3 KB) - added by Alex Hagen-Zanker <ahh34@…> 5 years ago.
example of failing assert

Download all attachments as: .zip

Change History (6)

Changed 5 years ago by Alex Hagen-Zanker <ahh34@…>

Attachment: main.cpp added

example of failing assert

comment:1 Changed 5 years ago by Alex Hagen-Zanker <ahh34@…>

Summary: edge weights equal to distance_inf lead not correctly supported in dijkstraedge weights equal to distance_inf not correctly supported in dijkstra

comment:2 Changed 5 years ago by Jeremiah Willcock

Resolution: invalid
Status: newclosed

This is the intended behavior -- the graph logically is assumed to have all edges, with some of those (the ones that are not connected in the graph's topology) having infinite weight. See http://cpsc.ualr.edu/srini/DM/chapters/review5.3.html for an example; it is commonly used for shortest path algorithms. Thus, infinite-weight edges are treated as not existing at all since they are the same in the matrix representation. If you want an edge to be treated as active, give it a weight less than infinity. A scheme such as the one described at http://tex.stackexchange.com/questions/21022/what-is-the-difference-between-fil-and-fill will give you multiple levels of "infinity" to use for edge weights and path lengths.

comment:3 Changed 5 years ago by Alex Hagen-Zanker <ahh34@…>

Ok.It does not seem like a very robust way of ignoring edges. It feels wrong to me to not filter out non-edges at the outer-loop of the algorithm but to do at the most detailed levels of computation. Even having to redefine the plus operations. Do you not use filtered_graph for that? How about measures like in-degree and out-degree, won't you get the wrong numbers? How about the visitors that are called along the way won't they get issued with mis-information? For instance vertices may now be discovered even when they are not reachable. The documentation says that "each reachable vertex is discovered exactly once". But it does not tell us that unreachable vertices may also be discovered.

http://www.boost.org/doc/libs/1_51_0/libs/graph/doc/dijkstra_shortest_paths.html

Anyway the use of edge weights invalidates quite a bit of my comments in #7387, but I suppose you figured that already.

Sorry to ramble, it just seems very wrong to me.

comment:4 Changed 5 years ago by Alex Hagen-Zanker <ahh34@…>

The following is also not correct:

"... only those vertices in V - S that are discovered and therefore have a distance less than infinity..."

comment:5 Changed 5 years ago by Jeremiah Willcock

Resolution: invalidfixed

(In [80637]) Added wording that infinite-weight edges are not guaranteed to work correctly; fixes #7398

Modify Ticket

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