Le plus court chemin - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Article Dans Une Revue Interstices Année : 2005

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.
Fichier non déposé

Dates et versions

inria-00000908 , version 1 (08-12-2005)

Identifiants

  • HAL Id : inria-00000908 , version 1

Citer

Jean-Michel Hélary. Le plus court chemin. Interstices, 2005. ⟨inria-00000908⟩
144 Consultations
0 Téléchargements

Partager

Gmail Facebook X LinkedIn More