Opened 15 years ago

Closed 14 years ago

#1009 closed Bugs (fixed)

Improper overflow handling in shortest paths algorithms

Reported by: Douglas Gregor Owned by: Jeremiah Willcock
Milestone: Boost 1.34.1 Component: graph
Version: Boost 1.34.0 Severity: Problem
Keywords: Cc:

Description

As reported here

​http://lists.boost.org/boost-users/2007/05/28205.php

the Bellman-Ford shortest paths algorithm fails to compute correct results in some graphs containing negative cycles. The cause of the problem is the incorrect overflow handling in closed_plus, which is used to relax edges in the graph. The attached patch fixes the problem.

Attachments (1)

bellman-ford-neg-cycle.patch​ (2.9 KB ) - added by Douglas Gregor 15 years ago.
Fix handling of overflow

Download all attachments as: .zip

Change History (6)

by Douglas Gregor, 15 years ago

Attachment: bellman-ford-neg-cycle.patch​ added

Fix handling of overflow

comment:1 by Douglas Gregor, 15 years ago

Milestone: → Boost 1.34.1
Resolution: → fixed
Status: new → closed

comment:2 by anonymous, 15 years ago

Resolution: fixed
Status: closed → reopened

This solution breaks the floyd_warshall_all_pairs_shortest_paths (which uses this as the default BinaryPredicate) in the case that one of the parameters is infinity and the other parameter is a negative number.

comment:3 by Jeremiah Willcock, 14 years ago

Owner: changed from Douglas Gregor to Jeremiah Willcock
Status: reopened → new

comment:4 by Jeremiah Willcock, 14 years ago

Status: new → assigned

comment:5 by Jeremiah Willcock, 14 years ago

Resolution: → fixed
Status: assigned → closed

Probably fixed in r50808 (fix for #1164 which is also related to overflow handling).

Note: See TracTickets for help on using tickets.