Re: [igraph] Bug in igraph_get_shortest_paths_dijkstra for small edge weights

[Tamás Nepusz]

Hi Martin, 

Thanks for the heads up. You are probably right -- the Dijkstra implementation 
was adapted from the unweighted shortest path implementation where we employed 
the same trick to save a memset() operation initially, but of course this 
causes problems when one is working with very small weights. Feel free to file 
a bug report on Launchpad with the appropriate patch, and we will integrate it 
in the next minor igraph release (that is, 0.6.1).

Cheers,
-- 
T.


On Tuesday, 7 August 2012 at 01:43, Reed, Martin J wrote:

> 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-help mailing list
> address@hidden (mailto:address@hidden)
> https://lists.nongnu.org/mailman/listinfo/igraph-help
> 
> 
> Attachments: 
> - igraph-mod.diff
>