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 > [email protected] (mailto:[email protected]) > https://lists.nongnu.org/mailman/listinfo/igraph-help > > > Attachments: > - igraph-mod.diff > _______________________________________________ igraph-help mailing list [email protected] https://lists.nongnu.org/mailman/listinfo/igraph-help
