cours terminale ES enseignement de spécialité

Introduction à la théorie des graphes

III - problèmes de plus court chemin

La recherche du meilleur itinéraire que ce soit en distance, en temps ou en coût d'un point à un autre peut être modélisée par la recherche du plus court chemin dans un graphe.

Dans ce paragraphe, on s'intéresse à la recherche d'un plus court chemin dans un graphe entre deux sommets donnés.

1 - Graphe pondéré

définition

On appelle graphe pondéré, un graphe (orienté ou non) dont les arêtes ont été affectées d'un nombre appelé poids (ou coût).

Par analogie avec la matrice d'adjacence, on peut définir la matrice des poids P(ai,j) du graphe, dont les coefficients ai,j correspondent aux poids des arêtes (ou des arcs dans le cas d'un graphe orienté) : ai,j={0sii=js'il n'existe pas d'arêtes ( ou d'arc) entre les sommetsxietxjpi,jpi,jest le poids de l'arête ( ou de l'arc) entre les sommetsxietxj On utilise le symbole pour indiquer qu'il n'y a pas d'arêtes entre deux sommets.

exemple

Graphe pondéré : L'illustration svg n'est pas visible par votre navigateur.

Les sommets du graphe étant rangés dans l'ordre alphabétique la matrice des poids est :P=(0714080618011019041350990)


longueur d'un chemin

Soit C(x;y) un chemin (ou une chaîne) dans un graphe pondéré G du sommet x vers le sommet y. La longueur de ce chemin est égale à la somme des poids de chacun arcs ( ou de chacune des arêtes) qui le constituent.

remarque

Cette définition généralise la définition de la longueur d'une chaîne dans un graphe non pondéré, il suffit d'attribuer un poids égal à 1 à chaque arête du graphe.

Dans le graphe précédent, la longueur du chemin A-E-F-G est 14+19+4=37.

2 - algorithme de dijkstra

Si on souhaite déterminer le plus court chemin entre deux sommets d'un graphe, on peut essayer d'énumérer tous les chemins possibles entre ces deux sommets et calculer leurs longueurs. Mais avec un graphe de taille importante, ceci risque de devenir rapidement impossible.
Pour résoudre ce problème, on fait appel à des algorithmes.

En terminale ES, on n'étudie que le cas particulier où les poids de tous les arcs sont des réels positifs.

E. W. Dijkstra (1930-2002) a proposé en 1959 un algorithme qui permet de déterminer le plus court chemin entre deux sommets d'un graphe connexe pondéré (orienté ou non) dont le poids lié aux arêtes est positif.

L'algorithme dû à Dijkstra est basé sur le principe suivant :

Si le plus court chemin reliant le sommet de départ s0 à un autre sommet S passe par les sommets s1, s2, …, sk alors, les différentes étapes sont aussi les plus courts chemins reliant A aux différents sommets s1, s2, …, sk.

On construit de proche en proche le chemin cherché en choisissant à chaque itération de l'algorithme, un sommet si du graphe parmi ceux qui n'ont pas encore été traités, tel que la longueur connue provisoirement du plus court chemin allant de s0 à si soit la plus courte possible.

L'algorithme comporte une phase d'initialisation. À chaque sommet on attribue un poids qui vaut 0 pour le sommet de départ et infini pour les autres sommets.

l'algorithme de Dijkstra

Soit G un graphe connexe dont les arêtes sont pondérées par des nombres positifs.

notations :

initialisation :

Pour ChaquexSFaireδs(x)On attribue un poids à chacun des sommetsx
δs(s0)0Le poids du sommet s0 est nul
XSLa liste des sommets restant à traiter est initialisée à S
ELa liste des sommets déjà traités vide

traitement :

exemple

Le graphe ci-dessous représente le réseau routier d'une région qui prend en compte le sens de la circulation, chaque arc représente une route à sens unique dont le poids est la distance en kilomètre entre deux sommets. Quel est l'itinéraire le plus court qui relie A à H ?

Algorithme de Dijkstra : L'illustration svg n'est pas visible par votre navigateur.

Vous pouvez observer le déroulement de l'algorithme de Dijkstra pas à pas en cliquant sur le bouton.

Pour faciliter la recherche du plus court chemin il est commode de présenter les résultats dans un tableau

ABCDEFGHSommets sélectionnésCommentaires
 0 

A (0)

On affecte le poids 0 au sommet origine (A) et on attribue provisoirement un poids aux autres sommets.
Le sommet A de poids 0 est selectionné.
7 (A)14 (A)

B (7)

Le sommet A de poids 0 ayant été selectionné, on marque provisoirement les sommets B (0+7<) et E (0+14<) adjacents à A.
On selectionne le sommet B de poids minimal. Le prédécesseur de B est A.
15 (B)14 (A)

E (14)

B de poids 7 ayant été selectionné, on marque provisoirement le sommet C(7+8<) adjacent à B.
On selectionne le sommet E de poids minimal. Le prédécesseur de E est A.
15 (B)33 (E)

C (15)

E de poids 14 ayant été selectionné, on marque provisoirement le sommet F (14+19<) adjacent à E.
On selectionne le sommet C de poids minimal. Le prédécesseur de C est B.
21 (C)33 (E)

D (21)

C de poids 15 ayant été selectionné, on marque provisoirement le sommet D (15+6<) adjacent à C.
On selectionne le sommet D de poids minimal. Le prédécesseur de D est C.
33 (E)
32 (D)

F (32)

D de poids 21 ayant été selectionné, on marque provisoirement le sommet F (21+11<33) adjacent à D.
On selectionne le sommet F de poids minimal. Le prédécesseur de F est D.
36 (F)45 (F)

G (36)

F de poids 32 ayant été selectionné, on marque provisoirement les sommets G (32+4<) et E (32+13<) adjacent à F.
On selectionne le sommet G de poids minimal. Le prédécesseur de G est F.
45 (F)
44 (G)

H (44)

G de poids 36 ayant été selectionné, on marque provisoirement le sommet H (36+8<45).
On selectionne le sommet H de poids minimal. Le prédécesseur de H est G.

  • L'algorithme de Dijkstra fournit les longueurs des plus courts chemins du sommet origine aux différents sommets.
  • Pour déterminer le plus court chemin du sommet origine à un sommet x, il suffit de remonter la liste des prédécesseurs en partant du sommet x.

Le sommet final H étant marqué, pour lire la chaîne de poids minimal, on part de H et on remonte la chaîne en suivant les prédécesseurs. HGFDCBA.

Le trajet le plus court pour aller de A à H est A - B - C - D - F - G - H, la distance parcourue est 44 km.


pour s'entrainer

Dans le graphe pondéré ci-dessous, les poids des arêtes sont déterminés de manère aléatoire. Un papier un crayon, et vérifiez vos résultats ...

Algorithme de Dijkstra : L'illustration svg n'est pas visible par votre navigateur.

Vous pouvez vérifier le déroulement de l'algorithme de Dijkstra pas à pas en cliquant sur le bouton.


Télécharger le polycopié du cours :

   |   


Chaîne, cycle <<précédent

[ Accueil ]


Les documents présentés ne sont pas libres de droits. Vous pouvez les télécharger et diffuser (en indiquant la provenance) à condition de ne pas en faire un usage commercial.