graph/path: implement standard improvements to Yen's KSP algorithm #2005
Conversation
kortschak
changed the title
| @@ -329,6 +329,33 @@ var yenShortestPathTests = []struct { | |||
| {1, 4, 5, 2, 3, 6}, | |||
| }, | |||
| }, | |||
| { | |||
There was a problem hiding this comment.
What is this new test for? It passes without the implementation change.
There was a problem hiding this comment.
It catches an incorrect implementation of the early termination optimisation.
When I read the description of the optimisation, I thought that it was maybe possible to terminate once there is enough paths in the list of potential shortest paths.
I tried to check this idea with the existing tests, and found that there was no case where a new potential path is shorter than all the remaining potential paths computed in previous iterations.
However, this case can actually occur in practice, as demonstrated by the test case.
There was a problem hiding this comment.
I'd like the changes that are not required for the optimisations to be backed out.
graph/path/yen_ksp.go
Outdated
| @@ -111,7 +111,16 @@ func YenKShortestPaths(g graph.Graph, k int, cost float64, s, t graph.Node) [][] | |||
| if len(best.path) <= 1 || best.weight > cost { | |||
| break | |||
| } | |||
| if neededPaths := k - i; k >= 0 && len(pot) >= neededPaths && best.weight == pot[neededPaths-1].weight { | |||
There was a problem hiding this comment.
This is the second optimisation? These should be in separate commits.
This optimisation skips computation of some shortest paths that are definitely redundant (already computed earlier). See https://en.wikipedia.org/wiki/Yen%27s_algorithm#Improvements for details.
Potential paths computed in future iterations can never be shorter than the shortest path computed in the current iteration, so if we have already computed `k-i` potential paths with the same minimal weight, we can stop early. See also https://en.wikipedia.org/wiki/Yen%27s_algorithm#Improvements
This test shows that a potential path computed in a future iteration can be shorter than the 2nd shortest computed in the current iteration.
BarrensZeppelin
force-pushed
the
graph/yenksp-opt
branch
from
8f49051 to
d5e11d4
Compare
BarrensZeppelin
force-pushed
the
graph/yenksp-opt
branch
from
d5e11d4 to
c14e6c1
Compare
I implemented two common optimizations for Yen's algorithm that can reduce the number of calls to the shortest path subroutine: https://en.wikipedia.org/wiki/Yen%27s_algorithm#Improvements
Split from #2004