K plus courts chemins dans Vcsn
From LRDE
- 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).