Menu

#161 DijkstraDistance does not terminate when targets are found

open
nobody
5
2010-08-03
2010-08-03
eike
No

CLASS AFFECTED: DijkstraDistance
DESCRIPTION: When singleSourceShortestPath is called with a nonempty Collection<V> targets, the algorithm does not terminate, when the targets are found, but expands the whole graph.
REPEAT BY: Compare running time in a small graph and a larger supergraph for the same source/target pair.
SAMPLE FIX:
The stopping condition of the main while-loop seems to be wrong.
Replace
<code>while (!sd.unknownVertices.isEmpty() && (sd.distances.size() < numDests || !to_get.isEmpty()))</code>
with
<code>while (!sd.unknownVertices.isEmpty() && sd.distances.size() < numDests && !to_get.isEmpty())</code>

Discussion


Log in to post a comment.

MongoDB Logo MongoDB