Lycée > Terminale > Mathématiques > Recherche du plus court chemin

Recherche du plus court chemin

Fiche de cours
Quiz
Profs en ligne
Videos
Application mobile

Objectif(s)

Recherche du plus court chemin sur un graphe pondéré connexe.

1. Définitions

► Chaînes, chaînes eulériennes, cycle eulérien

Une chaîne est une liste ordonnée de sommets adjacents d’un graphe. La longueur de cette chaîne est le nombre d’arêtes qui la compose.

Une chaîne fermée est une chaîne dont l’origine et l’extrémité sont confondues.

Une chaîne eulérienne est une chaîne contenant toutes les arêtes du graphe une fois et une seule.

Un cycle eulérien est une chaîne fermée contenant toutes les arêtes du graphe une fois et une seule.

Graphe 1

A - B - C - D est une chaîne du graphe 1, elle est de longueur 3.
A - B - C - D - A est une chaîne fermée.

► Graphes étiquetés

Un graphe étiqueté est un graphe orienté où chaque arête est étiquetée par un nombre ou un mot (un dessin…).

Graphe 2

► Graphes pondérés

Un graphe pondéré est un graphe étiqueté de nombres positifs uniquement.

Chaque nombre est appelé poids d’une arête.

Le poids d’une chaîne est la somme des poids des arêtes qui la composent.

Graphe 3

► Graphes connexes

Un graphe est connexe si pour chaque paire de sommets il existe au moins une arête reliant ces deux sommets.

Graphe 4

Les graphes 1, 2 et 3 sont des graphes connexes.
Graphe 4 ci-contre n’est pas un graphe connexe.

2. Propriétés : théorème d’Euler

Un graphe connexe admet une chaîne eulérienne si et seulement si le nombre de ses sommets de degré impair est 0 ou 2.
• S'il n’y a aucun sommet de degré impair, la chaîne est fermée (départ = arrivée, cycle eulérien).
• S’il y a deux sommet de degré impair, l’origine de la chaîne est l’un de ces sommets, l’extrémité étant l’autre sommet (chaîne eulérienne).

Application : rappel les ponts de Königsberg (leçon Graphe 1).

Le degré de chaque sommet est impair. Il n’y a pas de chaîne eulérienne. Il n’est pas possible de traverser les 7 ponts une fois et une seule pour revenir à son point de départ.

Pour que l’on puisse faire un chemin ramenant le promeneur au point de départ, il faudrait que le nombre de ponts pour chaque île et chaque rive soit pair.

Si on enlève la contrainte de revenir au point de départ, il faudrait que deux des sommets au plus (le départ et l’arrivée) aient un nombre impair de ponts.

3. Recherche du plus court chemin

a. Définition

La plus courte chaîne entre deux sommets est parmi toutes les chaînes qui relient ces deux sommets celle qui est de poids minimal.

b. Algorithme de Dijkstra

La méthode est expliquée de deux façons.
Directement sur le graphe (si ce graphe est suffisamment simple) ou par construction d’un tableau (dès que le chemin devient un peu long).

► Algorithme de Dijkstra directement sur le graphe

Graphe 5	Pour le graphe ci-contre recherche du plus court chemin depuis A jusqu’à D. On écrira 0 en A (aller de A en A sans se déplacer). Puis (schéma suivant), deux possibilités : - soit aller en B, - soit aller en E. On ignore les autres points.
Graphe 6	On arrive en B depuis A en avançant de 4. En B on écrit (4A). On arrive en E depuis A en avançant de 2. En E on écrit (2A). Les possibilités de déplacement depuis A sont épuisées.
Graphe 7	On s’occupe des points où l’on est arrivé : - depuis B, on peut aller en E (ce qui ferait 5 donc plus que directement depuis A ce qui ne présente aucun intérêt), en C ou en D. - depuis E, on peut aller en B, ce qui diminue le parcours A-B. On barre la valeur précédente que l’on remplace par (3E). On peut aussi aller en C ou en D. On marque chacune des valeurs (voir schéma) en additionnant la longueur de l’arête parcourue et la valeur obtenue précédemment, on barre éventuellement celles qui seraient plus grandes.
Graphe 8	Il ne reste plus que de C à D, on constate que la longueur totale de ce chemin est plus courte que celles déjà obtenues que l’on barre. On peut alors dire que le chemin le plus court a une longueur de 7, que pour arriver en D il faut venir de C, depuis B, en venant de E depuis A. Le meilleur parcours est donc A - E - B - C - D.

► Algorithme de Dijkstra dans un tableau

Avec le même graphe, recherchons le plus court chemin depuis A jusqu’à D.

• Dans un tableau, placer en ligne les sommets par ordre alphabétique, le premier sommet étant le point de départ, le dernier le point d’arrivée (ce qui peut ne pas respecter l’ordre alphabétique pour ces deux là).

• Ligne n°1, dans la colonne A écrire 0 car c’est la distance lorsque l'on va de A à A sans se déplacer.
On écrit ∞ dans chacune des autres colonnes de cette ligne car pour aller de A à A sans se déplacer on donne une distance infinie aux autres points.
En fin de tableau, dans la colonne résultats, on écrit A car c’est le point qui permet d’avoir la meilleure distance depuis A.
A ne sera plus utilisé, on raye toute sa colonne (voir tableau).

• Ligne n°2 : on écrit les deux distances des points joignables depuis A.
Depuis A, on ne peut atteindre les autres points, on les affecte d’une distance ∞.
Depuis A, la plus courte distance de parcours est E que l’on écrit dans la colonne des résultats.

• Ligne n°3 : on raye les colonnes qui ne seront plus utilisées, on reporte les nouveaux calculs de distance (depuis les points B ou E).
On raye (ou on ne garde pas) les distances plus grandes.
On reporte B meilleur point, car sa distance depuis A est la plus courte.

• Ligne n°4 : depuis B et sa meilleure longueur (depuis A), on atteint C avec la meilleure distance.

• Ligne n°5 : depuis C, la longueur obtenue vers D, le point d’arrivée, est meilleure que celles obtenues depuis B ou E.
Alors le chemin le plus court a une longueur de 7, pour arriver en D : il faut venir de C, depuis B, en venant de E depuis A.

Le meilleur parcours est donc A - E - B - C - D.