K shortest-paths in Vcsn

From LRDE

(Redirected from Publications/201614-Seminar-Piat)

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).