K shortest-paths in Vcsn

From LRDE

Revision as of 17:06, 9 January 2018 by Bot (talk | contribs) (Created page with "{{CSIReport | authors = Sébastien Piat | title = K shortest-paths in Vcsn | year = 2016 | number = 1614 | abstract = When trying to retrieve multiple shortest paths in a grap...")
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

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