Mathématiques 2: Géométrie
Les graphes
Algorithme de Dijkstra

1. Introduction

L'algorithme de Dijkstra détermine le trajet optimal entre deux points.

On considère donc un graphe pondéré orienté ou non et on cherche à optimiser un chemin d'origine O (entrée) et d'extrémité S (sortie).

On note bien que lorsque'un graphe est orienté, il doit alors suivre les sens autorisés indiqués.

2. L'algorithme de Dijkstra

• On affecte le point d'entrée du poids 0,

• Si un sommet est adjacent et joignable, on l'affecte de sa distance au point d'entrée en indiquant la provenance à droite du poids correspondants,

• Les sommets non adjacents ne sont pas considérés. On les note symboliquement par . ou ∞

• On "fixe" Se premier sommet jugé optimum , puis on recommence l'inération à partir de ce sommet.

Tant qu'on a pas fixé un sommet, on repère le point de poids plus faible et on fixe ce point:

. Si ce poids est inférieur au poids précédemment considéré, on considère ce nouveau poids suivi de sa provenance.
. Si le poids est identique ou supérieur, on conserve l'ancien et sa provenance.

• En remontant les points fixés, on trouve le trajet optimum cherché.

On utilise en général un tableau. Dans ce tableau, on fixe, à chaque étape, les sommets considérés optimums.

Comme pour la lecture d'un graphe, on place les sommets de gauche à droite. Mais l'ordre des sommets dans le tableau est tout à fait arbitraire.

Exemple 1

Étudions l'algorithme de Dijkstra sur un exemple de graphe orienté :

Il s'agit de se rendre de C à E en minimisant les temps de parcours indiqués.



• On affecte le point d'entrée C du poids 0.

• On "fixe" C et on ferme la colonne C.

• Les sommet adjacents et joignables sont B, F et D. On les affecte de leurs distances à C en indiquant la provenance à droite du poids correspondants,

• À partir de C, On repère le ponts de poids le plus faible : c'est ici 2C correspondant au sommet D.

On fixe ce point, et on ferme sa colonne,

• On inscrit en ligne suivante les distances de ce point D aux autres sommets adjacents du graphe à l'exception des points déjà fixés , ce sont F et A seulement.

Pour tout point non adjacent, on inscrira un poids infini (∞).

C	B	F	D	E	A	Fixés
0	9C	6C	2C	∞	∞	C
	9C	5D		∞	11D	D
	8F			∞	11D	F
				∞	10B	B
					0	A

• Depuis C :

B: est adjacent, on lui reconduit 9C . F: est adjacent, on lui inscrit 6C.
D: est adjacent, on lui inscrit 2C.
Finalement, on fixe D de poids 2C et on ferme sa colonne.

• Depuis D :

B: n'est pas adjacent, on lui reconduit 9C .
F: On lui inscrit 5D (5 = 2 + 3).
A: On lui inscrit 11D (11 = 2 + 9)
Finalement, on fixe F de poids 5 et on ferme sa colonne.

• Depuis F :

B: est pas adjacent, on lui inscrit 8F (8 = 5 + 3).
Mais pour B, on lui avait lui reconduit 9C,
On lui inscrit donc un nouveu poids 8F.
A: On lui inscrit 11F (11 = 5 + 6)
Finalement, on fixe B de poids 8 et on ferme sa colonne.

• Depuis B:

A: est adjacent, on lui inscrit 10B (10 = 8 + 2).
Mais pour A, on lui avait inscrit 11D et 11F
On lui inscrit donc inscrit donc un nouveu poids 10B.
Finalement, on fixe A de poids 10 et on ferme sa colonne.

• Depuis A:

Pour se rendre à la destination finale E, il n y a qu'un seul choix, c'est le trajet AE de poids 10.

• Chemin optimal :



E, point de sortie, provient de A
A, provient de B
B provient de F
F provient de D
D provient de C : point d'entrée.

On remonte en arrière les sommets fixés :

D'où:

Le chemin le plus court est C D F B A E de poids 14.

Exemple 2

On considère le graphe non orienté suivant:


On veut trouver la distance minimale de E à S tout en minimisant également le nombre de sommets obtenus.

E	A	B	C	D	F	S	point fixé
0	4E	2E	∞	∞	∞	∞	E
	4E		7B	∞	5B	∞	B
			7A/7B	9A	5B	∞	A
			7B	9A		13F	F
				8C		12C	C
						12C/12D	D
						0	S

Chemin optimal :

On remonte en arrière les sommets fixés :

S, point de sortie, provient de C
C provient de B
B provient de E : point d'entrée.

D'où :

Le chemin le plus court est: E B C S, de poids 12.

Cette solution n'est pas unique :

• En C, on a: 7A = 7b. On peut donc choisir A plutôt que B:

Une seconde solution de même poids 12 est : E A C S.

• En S, le chemin CS est équivalent au chemin CDS qui sont tous de valeur 5. On peut donc prendre D au lieu de C:

Une troisième solution de même poids 12 est : E A C D S.

• En tout, on a 4 possiblités toutes de mêmepoids 12:

E B C S , E A C S, E B C D S, E A C D S.

• Avec un minimum de sommets, on garde les deux solutions:

E B C S ou E A C S.

Exemple 3

On considère le graphe non orienté suivant:


On veut trouver la distance minimale de A à G. Les arêtes représentent des temps en secondes.

	A	B	C	D	E	F	G
point fixé	0	∞	∞	∞	∞	∞	∞
A(0)	0	2A	1A	∞	∞	∞	∞
C(1)		2A	0	5C	4C	6C	∞
B(2)		0		5C/3B	4C/5B	6C	∞
D(3)				0	4C/5B/6D	6C/9D	8D
E(4)					0	6C/9D/5E	8D
F(5)						0	8D/7F
G(7)							0

Chemin optimal :

On remonte en arrière les sommets fixés :

G, point final (goal), provient de F
f provient de E
E provient de C
Cprovient de A : point de départ.

D'où :

Le chemin le plus rapide de A à G est: ACEFG, de durée 7 secondes.

  Edsger Wybe Dijkstra est un mathématicien et informaticien néerlandais. Il est né à Rotterdam en 1930 et mort à Nuenen en 2002.

Après des études de physique théorique, il s'engage dès 1955 dans le domaine de l'informatique. En 1959, en théorie des graphes, Dijkstra a publié l'algorithme qui porte son nom.

Cet algorithme sert à résoudre le problème du plus court chemin. Il s'applique à des graphes connexes avec des poids réels positifs.