K plus courts chemins dans Vcsn

From LRDE

Revision as of 17:06, 9 January 2018 by Bot (talk | contribs) (Created page with "{{CSIReportFR | authors = Sébastien Piat | titre = K plus courts chemins dans Vcsn | year = 2016 | number = 1614 | resume = Lorsque l'on cherche à obtenir plusieurs plus cou...")
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

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