K plus courts chemins dans Vcsn

Auteurs

Sébastien Piat

Type

techreport

Année

2017

Numéro

1701

Résumé

Le calcul des K plus courts chemins dans un automate peut être très coûteux, surtout sur des automates énormes comme ceux utilisés en linguistique. Ainsiaprès avoir implémenté l'une des solutions considérée comme l'état de l'art (appelée l'algorithme de Yen) dans Vcsn, l'étape suivante était l'implémentation de la meilleure solution pour ce calcul sur des automates avec des cycles: Eppstein. Ce travail va décrire nos différentes implementations et comparer leurs performances.