| Issue |
Quadrature
Number 72, Avril-Juin 2009
|
|
|---|---|---|
| Page(s) | 22 - 28 | |
| Section | Algèbre | |
| DOI | https://doi.org/10.1051/quadrature/2009009 | |
| Published online | 25 mars 2009 | |
Quadrature n° 72 (2009) 22-28
Algèbres tropicales et plus court chemin
Abstract
Chercher le plus court chemin sur un graphe est un problème algorithmique complexe. Ce texte de TIPE propose de revisiter ce problème à la lueur de la géométrie tropicale et d'obtenir la résolution via un système linéaire sur une certaine algèbre. La fin du texte est consacrée à une implémentation de cette solution théorique.
© EDP Sciences, 2009