Modify

Ticket #1700 (closed Patches: fixed)

Opened 6 years ago

Last modified 6 years ago

graph/floyd_warshall_shortest.hpp.patch

Reported by: eric80@… Owned by: dgregor
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

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

Change History

Changed 6 years ago by eric80@…

comment:1 Changed 6 years ago by dgregor

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

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

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.