K plus courts chemins dans Vcsn

Auteurs

Sébastien Piat

Type

techreport

Année

2016

Numéro

1614

Résumé

Lorsque l'on cherche à obtenir plusieurs plus courts chemins d'un graphe, il n'est pas intéressant de lancer plusieurs fois un algorithme de plus court chemin puisqu'il retournerait toujours le même chemin. Plusieurs algorithmes existent pour pallier ce problème. L'un d'eux, l'algorithme de Yen, cache des transitions dans le graphe entre chaque calcul de plus court chemin. Ce travail présentera l'implementation de cet algorithme dans Vcsn ainsi que les différentes techniques d'optimisations envisagées (notamment l'implementation d'un ensemble creux).