[igraph] Bug in igraph_get_shortest_paths_dijkstra for small edge weights

[Reed, Martin J]

Hi,

I have found a bug in igraph_get_shortest_paths_dijkstra() from 
structural_properties.c (and thus also the other Dijkstra implementations in 
the same file). The bug is only serious for small values in the weights vector.

The problem is caused by using zero to signify infinity and thus using 1.0 to 
actually signify zero. In part of the implementation there are lines like:

VECTOR(dists)[tto] = altdist+1.0;

(and other points where 1.0 is added or taken away).

If the distances are small (very small compared to 1.0) this causes significant 
error. In my case I was porting a Max flow algorithm I had previously written 
using the Boost graph library that starts with VERY small edge weights so that

altdist + 1.0 == 1.0

due to numerical precision limits.

The affect of this in my case was either a continual loop later in the 
igraph_get_shortest_paths_dijkstra() or in the same function, a crash with 
"EXC_BAD_ACCESS, Could not access memory".

I would like to propose a solution that I would like others to test, see my 
diff (against most recent nightly build). Essentially I have fixed -1 as 
infinity and left the "dists" vector elements at zero to mean zero (as Dijkstra 
intended!). I do not see any problem with this (but then many did not see the 
problem with the current implementation!) so careful inspection appreciated.

I have not filed a bug report on launchpad yet as I would like comment on this 
list before I do. Maybe this is a feature not a bug ;-)  If people agree I will 
apply the change to other places in structural_properties.c and post a full 
diff to launchpad with the bug report.

Diff is below.

Martin Reed, University of Essex, UK

igraph-mod.diff
Description: igraph-mod.diff