search

FubarDevelopment / QuickGraph

Fork of https://quickgraph.codeplex.com/
Microsoft Public License
9 stars 2 forks source link

CP-16473: bug in HoffmanPavleyRankedShortestPathAlgorithm #98

Open fubar-coder opened 6 years ago

fubar-coder commented 6 years ago

From unknown CodePlex user on Monday, 22 February 2010 04:07:21

In HoffmanPavleyRankedShortestPathAlgorithm.cs the algorithm can get caught in the while-loop starting at line 107. If the path found contains a cycle, it is not added to the list of found pathes, but still its deviation pathes are added to the queue. So it may happen (and does in an example that I encountered), that ComputedShortestPathCount does not increase, the queue grows and grows and the loop never exits. Shouldnt you put the // append new deviation paths block under the condition if (!EdgeExtensions.HasCycles<TVertex, TEdge>(path)) ?

TestCrash.zip

fubar-coder commented 6 years ago

Form unknown CodePlex user on Monday, 27 February 2012 01:16:52

Attached is an example project that replicates the hang

fubar-coder commented 6 years ago

Form unknown CodePlex user on Saturday, 23 February 2013 16:46:05

" Shouldnt you put the "// append new deviation paths" block under the condition "if (!EdgeExtensions.HasCycles<TVertex, TEdge>(path))" ?"

If you do that it won't find all the shortest paths, e.g., where you wish to travel from A to B, which are both points connected in a loop, and the shortest path is one way round the loop, but there is a longer path going the other way.