K plus courts chemins dans Vcsn
From LRDE
The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.
- 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).