Counting number of shortest paths in SSSP algos

[avdgrinten]

While looking at the fix of #98, I noticed the following bug: In Dijkstra.cpp we optionally count the number of shortest paths to all nodes. We do this by checking

distances[v] == distances[u] + w

this is actually wrong if the weights are not integer (e.g. 0.1 + 0.2 does not compare equal to 0.3 for double-precision floats).

I do not think there is an obvious fix for this problem. Things that we could do are:

• Keep the code. It is simple and works for integers. Document that the code does not work for floating point numbers and/or emit a warning if we encounter this case.

• Perform an epsilon comparison (i.e. consider two paths equal if their length only differs by some epsilon). This will require more complex changes to the case where the distance to a node is updated: We can no longer throw away all predecessors as we have to keep those that are still within epsilon of the new distance. This needs non-constant time. Furthermore, epsilon errors can accumulate along a path.

I am not sure how important path counting is and if there are any users of this feature (especially for floating point weights). Please comment on if you think that a real fix to this problem is worthwhile.

[hmeyerhenke]

I have a bad feeling with not supporting floating point weights. At least this problem must be documented properly.

Do you see an elegant way for a dual solution in which the user can choose between the integer and the floating point version? Without much code duplication and only negligible performance impact?

[clintg6]

I just tested networkit's implementation against both igraph and networkx using floating point edge weights and got the exact same paths.