K shortest-paths in Vcsn
From LRDE
(Redirected from Publications/201614-Seminar-Piat)- Authors
- Sébastien Piat
- Type
- techreport
- Year
- 2016
- Number
- 1614
Abstract
When trying to retrieve multiple shortest paths in a graph, we cannot simply run a shortest path algorithm multiple times as it would always retrieve the same. Some algorithms exist to solve this problem. One of them, the Yen algorithm hides transitions in the graph between each calculation to retrieve the correct paths. This work will present how it was implemented in Vcsn and the optimization techniques we tried on this algorithm (including the implementation of a sparse set).