graph/path: implement standard improvements to Yen's KSP algorithm#2005
graph/path: implement standard improvements to Yen's KSP algorithm#2005BarrensZeppelin wants to merge 3 commits into
Conversation
kortschak
left a comment
There was a problem hiding this comment.
Please revise this to be the two optimisations in separate commits with no other changes. We can do the other changes later if they merit it.
Note that the format of commit messages starts the sentence fragment with a lower case.
| {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.
| 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.
8f49051 to
d5e11d4
Compare
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