Skip to Main content Skip to Navigation
Journal articles

Le plus court chemin

Résumé : Il est courant, lorsque l'on cherche à se rendre d'un point à un autre dans un réseau (routier, par exemple), de chercher le plus court chemin, c'est-à-dire celui dont la distance est la plus petite. Si le nombre de trajets possibles entre le point de départ et le point d'arrivée est faible, il suffira de calculer les longueurs de chacun des trajets - en additionnant la longueur des liens qui le composent - et de comparer directement les longueurs obtenues. Mais une telle solution exhaustive devient rapidement impraticable si le nombre de trajets possibles est grand. Heureusement, il existe des algorithmes qui évitent d'avoir à calculer tous les trajets possibles. Pour cela, ils mettent en œuvre diverses stratégies.
Complete list of metadata

https://hal.inria.fr/inria-00000908
Contributor : Jean-Michel Hélary <>
Submitted on : Thursday, December 8, 2005 - 9:42:19 AM
Last modification on : Wednesday, May 16, 2018 - 11:23:10 AM

Identifiers

  • HAL Id : inria-00000908, version 1

Collections

Citation

Jean-Michel Hélary. Le plus court chemin. Interstices, INRIA, 2005. ⟨inria-00000908⟩

Share

Metrics

Record views

126