Modify

Opened 10 years ago

Closed 9 years ago

#1700 closed Patches (fixed)

graph/floyd_warshall_shortest.hpp.patch

Reported by: eric80@… Owned by: Douglas Gregor
Milestone: Boost 1.36.0 Component: graph
Version: Boost 1.34.1 Severity: Problem
Keywords: Cc:

Description

The "floyd_warshall_dispatch" function sometimes tries to pass in an edge weight of infinity into the "combine" function in line 68, resulting in the wrong computational result if you use the default "combine" function. The correct behavior is to check the edge weights and if either of d[*i][*k] or d[*k][*j] is infinity, to skip the distance matrix update. Attached is the patch.

Attachments (1)

floyd_warshall_shortest.hpp.patch (966 bytes) - added by eric80@… 10 years ago.

Download all attachments as: .zip

Change History (2)

Changed 10 years ago by eric80@…

comment:1 Changed 9 years ago by Douglas Gregor

Resolution: fixed
Status: newclosed

(In [48611]) Fix handling of infinite weights in Floyd-Warshall algorithm. Fixes #1700

Modify Ticket

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