Chapitre 7. Plus courts chemins

Un des problèmes d’optimisation combinatoire parmi les plus connus est celui de la recherche d’un plus court chemin entre deux sommets donnés d’un graphe :
On peut formuler de manière semblable le problème de la plus courte chaîne dans un graphe non orienté. Ce problème a de nombreuses applications pratiques. Il apparaît souvent, de même que le problème de l’arbre couvrant minimum, en tant que sous-problème dans l’étude de problèmes d’optimisation combinatoire plus difficiles.
Ce problème n’est pas simple à résoudre si les poids sont quelconques. Par exemple, quand les poids valent —1, les chemins de s à t de poids 1 − |V (G)| sont les chemins hamiltoniens de s à t. Or décider si un tel chemin existe est un problème difficile (voir exercice 17(b) du chapitre 15).
Le problème devient plus facile quand les circuits ont un poids total non négatif, ce qui est le cas si les poids des arcs sont non négatifs :Définition 7.1. Soit G un graphe orienté (resp. non orienté) muni de poids . c est dit conservatif s’il n’existe pas de circuit (resp. de cycle) de poids total négatif.
Nous étudierons des algorithmes de résolution du problème du plus court chemin au paragraphe 7.1. Le premier autorise seulement des poids non négatifs tandis que le second s’applique quand les poids sont conservatifs. Ces algorithmes calculent en réalité les plus courts chemins de s à v pour tout v ∈ V (G), sans que cette généralisation n’augmente le temps de calcul. Le problème de la recherche des distances entre toutes les paires de sommets sera étudié au paragraphe 7.2…