Les grands problèmes de cheminement
Cheminement entre deux points x et y
Plusieurs problématiques peuvent être considérées lorsque l'on s'intéresse au cheminement entre deux points d'un graphe. La plus simple consiste à déterminer si un chemin entre x et y existe. On veut savoir s'il est possible de se rendre d'un point x à un point y en utilisant un (ou plusieurs) chemin(s). Ce sont des problèmes d'existence de chemins.
Définition : Longueur d'un chemin
Dans un graphe valué (X,E,V) la longueur d'un chemin ayant pour origine x et pour extrémité y est la somme des valeurs des arcs qui le composent.
Selon les valeurs qui sont mises sur les arcs, la longueur d'un chemin peut représenter une distance ou une durée ou un coût ou encore un nombre d'arcs, tout arc ayant la valeur 1 (on comptabilise alors, par exemple, des correspondances dans un réseau de transport).
Définition : Chemins minimaux et maximaux
Dans un graphe valué (X,E,V), un plus court chemin entre x et y est un des chemins du graphe ayant pour origine x et pour extrémité y dont la longueur est la plus petite. Par convention, la longueur du plus court chemin entre x et y vaut +∞ s'il n'existe pas de chemin entre x et y.
Dans un graphe valué (X,E,V), un plus long chemin entre x et y est un des chemins du graphe ayant pour origine x et pour extrémité y dont la longueur est la plus grande. Par convention, la longueur du plus court chemin entre x et y vaut -∞ s'il n'existe pas de chemin entre x et y.
Définition : Problématique des problèmes de cheminement
Première famille de problèmes de cheminement : x et y sont fixés
On cherche un chemin optimal entre x et y (optimal pouvant signifier minimal ou maximal ou tout simplement "existence").
Deuxième famille de problèmes de cheminement : x est fixe et y est quelconque (ou x est quelconque et y fixe)
On cherche un chemin optimal (minimal ou maximal ou existant) de x à n'importe quel autre sommet.
On peut vouloir simplement la valeur de ce plus court chemin ou avoir la description complète du chemin.
Troisième famille de problèmes de cheminement : x et y sont quelconques
On cherche la valeur du chemin optimal (minimale ou maximale ou existence) entre tout point x et tout point y.
Il est à noter que la première famille est un cas particulier de la deuxième famille.
Souvent on utilise un algorithme de la deuxième famille pour résoudre les problèmes de la première famille. Si on cherche, par exemple, les plus courts chemins de x à n'importe quel point, il suffit de s'arrêter dès que l'on a traité le point y.
Il existe de très nombreux algorithmes de cheminement.
Certains sont plus rapides sur les graphes qui ont beaucoup d'arcs, d'autres sont plus rapides sur les graphes qui ont peu d'arcs.
Dans ce module de base, nous nous contentons d'un petit échantillon d'exemples.
