K shortest-paths in Vcsn

Authors

Sébastien Piat

Type

techreport

Year

2017

Number

1701

Abstract

The K shortest paths computation can be very time consuming especially when applied to the enormous automata used in linguistics. Hence, after having implemented one of the state-of-the-art solution to the problem (namely Yen's algorithm) in Vcsn, the next step was to implement the best known solution for automata with cycles: Eppstein. This work will describe our different implementations and compare their performances.