Problème du plus court chemin

Objectifs

• Définir le problème du plus court chemin
• Appliquer l'algorithme de Dijkstra

Cours

Problème du plus court chemin

Graphes

Problème du plus court chemin

Trouver le chemin le plus court entre deux sommets dans un graphe pondéré.

Algorithme de Dijkstra

Trouver le plus court chemin entre un sommet et tous les autres sommets du graphe.

Algorithme de Dijkstra

https://www.maths-cours.fr/methode/algorithme-de-dijkstra-etape-par-etape

Quel est le plus court chemin de M à S ?

Algorithme de Dijkstra

https://www.maths-cours.fr/methode/algorithme-de-dijkstra-etape-par-etape

https://www.maths-cours.fr/methode/algorithme-de-dijkstra-etape-par-etape

Initialiser les distances : infini sauf pour le départ M (0).

Algorithme de Dijkstra

https://www.maths-cours.fr/methode/algorithme-de-dijkstra-etape-par-etape

https://www.maths-cours.fr/methode/algorithme-de-dijkstra-etape-par-etape

M est visité (plus court chemin trouvé).

Algorithme de Dijkstra

https://www.maths-cours.fr/methode/algorithme-de-dijkstra-etape-par-etape

https://www.maths-cours.fr/methode/algorithme-de-dijkstra-etape-par-etape

Découverte des voisins de M.

Algorithme de Dijkstra

https://www.maths-cours.fr/methode/algorithme-de-dijkstra-etape-par-etape

https://www.maths-cours.fr/methode/algorithme-de-dijkstra-etape-par-etape

Visite du sommet le plus proche de M : N

Algorithme de Dijkstra

https://www.maths-cours.fr/methode/algorithme-de-dijkstra-etape-par-etape

https://www.maths-cours.fr/methode/algorithme-de-dijkstra-etape-par-etape

Découverte des voisins de N et mise à jour des distances.

L : 4 + 2 = 6 < 7 ; S : 4 + 8 = 12 < ∞

Algorithme de Dijkstra

https://www.maths-cours.fr/methode/algorithme-de-dijkstra-etape-par-etape

https://www.maths-cours.fr/methode/algorithme-de-dijkstra-etape-par-etape

Visite du sommet le plus proche de M : L

Algorithme de Dijkstra

https://www.maths-cours.fr/methode/algorithme-de-dijkstra-etape-par-etape

https://www.maths-cours.fr/methode/algorithme-de-dijkstra-etape-par-etape

Découverte des voisins de L et mise à jour des distances.

Algorithme de Dijkstra

https://www.maths-cours.fr/methode/algorithme-de-dijkstra-etape-par-etape

https://www.maths-cours.fr/methode/algorithme-de-dijkstra-etape-par-etape

Visite du sommet le plus proche de M : E

Algorithme de Dijkstra

https://www.maths-cours.fr/methode/algorithme-de-dijkstra-etape-par-etape

https://www.maths-cours.fr/methode/algorithme-de-dijkstra-etape-par-etape

Découverte des voisins de E.

Algorithme de Dijkstra

https://www.maths-cours.fr/methode/algorithme-de-dijkstra-etape-par-etape

https://www.maths-cours.fr/methode/algorithme-de-dijkstra-etape-par-etape

Visite du sommet le plus proche de M : S

Fin car le sommet de destination est visité.

Algorithme de Dijkstra

https://www.maths-cours.fr/methode/algorithme-de-dijkstra-etape-par-etape

Chemin minimal de M :

• à N : M → N (4)

• à L : M → N → L (6)

• à E : M → E (10)

• à S : M → N → L → S (11)

• à T : faire une itération de plus.

Algorithme de Dijkstra

• Initialisation

  • Distance infini pour tous les sommets sauf le sommet de départ (0).

• Itérations

  • Trouver le sommet non visité avec la distance la plus petite.

  • Mettre à jour les distances des voisins du sommet choisi.

  • Marquer le sommet choisi comme visité.

Exercice

Quel est le plus court chemin E → B et sa distance ?

Solution

	A	B	C	D	E	F
	∞	∞	∞	∞	0	∞
E	14	∞	9	∞	-	7
F	14	∞	9	22	-	-
C	11	∞	-	20	-	-
A	-	20	-	20	-	-

Chemin : E → C → A → B avec une distance de 20.

F pour passer en plein écran ou O pour afficher la vue d'ensemble.
Versions sans animation, plein écran, imprimable.

Exercices

Dijkstra

Appliquer l'algorithme de Dijkstra sur les graphes suivants :

Chemin : A → G

Solution

	A	B	C	D	E	F	G
	0	∞	∞	∞	∞	∞	∞
A	-	6	2	∞	∞	∞	∞
C	-	6	-	7	∞	∞	∞
B	-	-	-	7	∞	∞	∞
D	-	-	-	-	17	22	∞
E	-	-	-	-	-	22	19

Chemin : A → C → D → E → G avec une distance de 19

Chemin : A → F

Solution

	A	B	C	D	E	F
	0	∞	∞	∞	∞	∞
A	-	4	4	∞	∞	∞
B	-	-	4	∞	∞	∞
C	-	-	-	7	5	10
E	-	-	-	7	-	8
F	-	-	-	-	-	8

ou

	A	B	C	D	E	F
	0	∞	∞	∞	∞	∞
A	-	4	4	∞	∞	∞
C	-	4	-	7	5	10
B	-	-	-	7	5	10
E	-	-	-	7	-	8
F	-	-	-	-	-	8

Chemin : A → C → E → F avec une distance de 8

Chemin : D → I

Solution

	A	B	C	D	E	F	G	H	I
	∞	∞	∞	0	∞	∞	∞	∞	∞
D	3	∞	∞	-	7	∞	5	∞	∞
A	-	10	∞	-	4	∞	5	∞	∞
E	-	6	∞	-	-	5	5	7	∞
F	-	6	8	-	-	-	5	7	7
G	-	6	8	-	-	-	-	7	7
B	-	-	7	-	-	-	-	7	7
C	-	-	-	-	-	-	-	7	7
H	-	-	-	-	-	-	-	-	7

Chemin : D → A → E → F → I avec une distance de 7

Chemin : A → J

Solution

	A	B	C	D	E	F	G	H	I	J
	0	∞	∞	∞	∞	∞	∞	∞	∞	∞
A	-	85	217	∞	173	∞	∞	∞	∞	∞
B	-	-	217	∞	173	165	∞	∞	∞	∞
F	-	-	217	∞	173	-	∞	∞	415	∞
E	-	-	217	∞	-	-	∞	∞	415	675
C	-	-	-	∞	-	-	403	320	415	675
H	-	-	-	503	-	-	403	-	415	487
G	-	-	-	503	-	-	-	-	415	487
I	-	-	-	503	-	-	-	-	-	487

Chemin : A → C → H → J avec une distance de 487 km

Références

• https://fr.wikipedia.org/wiki/Probl%C3%A8me_de_plus_court_chemin
• https://fr.wikipedia.org/wiki/Algorithme_de_Dijkstra
• https://www.maths-cours.fr/methode/algorithme-de-dijkstra-etape-par-etape
• http://yallouz.arie.free.fr/terminale_cours/graphes/graphes.php?page=g3