--> Recherche du plus court chemin 1Notion de graphe pondéré Definition 1
En mathématiques un graphe est un schéma contenant des points appelés sommets, reliés ou non par des segments appelés arêtes. Exemple 1

0,0

A

B

C

D

E

F

G

Definition 2
Un graphe pondéré est un graphe pour lequel chaque arête est associée à un nombre réel positif. Exemple 2

0,0

H

M

C

U

7

8

9

14

11

Definition 3

Dans un graphe, on appelle chaîne une succession d'arêtes consécutives.
Dans un graphe pondéré, on appelle poids d'une chaîne la somme des poids des arêtes la composant.

Exemple 3 Dans le graphe précédent, le poids de la chaîne H - M - C - U est de

7+14+9 = 30

. 2Recherche du plus court chemin Le problème de la recherche du plus court chemin, à savoir, dans un graphe pondéré, d'une chaîne de poids minimum est très naturel, et se présente dans de nombreux domaines.
La méthode la plus immédiate est de considérer tous les chemins menant d'un point de départ à l'arrivée et de chercher le plus court, mais le nombre de calculs est très vite immense dès que le graphe possède de plus en plus de sommets et d'arêtes.
Edsger Wybe Dijkstra (mathématicien et informaticien néerlandais 1930 - 2002) a proposé en 1959 un algorithme qui permet de calculer le plus court chemin entre un sommet particulier et tous les autres. C'est l'un des plus efficaces encore à ce jour. Grâce à la puissance du traitement informatique, il est utilisé par les logiciels d'optimisation de trajets réels (applications GPS, sites de transport en commun, ...) ou virtuels (routage internet). 2.1Algorithme de Dijkstra Nous allons décrire comment trouver le chemin le plus court à partir d'un sommet d'un graphe pondéré.
À chaque utilisation de l'algorithme nous utiliserons une tableau, dont la première ligne est composée de l'ensemble des sommets et la dernière colonne formée par les sommets que nous allons choisir au fur et à mesure de l'exécution de l'algorithme.

Étape	Tâche à effectuer
$1$	• Placer tous les sommets du graphe dans la 1ère ligne d'un tableau. • Sur la 2ème ligne du tableau, écrire le coefficient 0 sous le sommet de départ et le coefficient $\infty$ sous les autres sommets.
$2$	• Repérer dans la ligne le sommet $X$ de coefficient minimal. • Commencer une nouvelle ligne et rayer la colonne vide sous $X$ .
$3$	• Pour chaque sommet $Y$ adjacent à $X$ , calculer la somme $p$ entre le coefficient de $X$ et du poids de l'arête reliant $X$ à $Y$ . • Si $p$ est strictement inférieur au coefficient de $Y$ dans la ligne précédente, inscrire $p$ dans la case correspondante de la colonne $Y$ . • Sinon, inscrire le coefficient de $Y$ de la ligne précédente, et compléter la ligne par des coefficients de la ligne précédente.
$4$	• S'il reste des sommets non sélectionnés, retourner à l'étape 2. • Sinon, passer à l'étape 5.
$5$	• La longueur minimale est le nombre lu sur la dernière ligne du tableau. La chaine de longueur minimale se trouve en lisant le tableau en repartant du dernier de sommet et en regardant de quel sommet l'on provient, et ainsi de suite jusqu'au sommet de départ.

2.2Exemple Un artisan part de chez lui à 7h05. Il doit arriver chez son client avant 7h30. Il a pour cela plusieurs trajets possibles en passant par diverses étapes. Les temps des trajets, en minutes, sont donnés dans le tableau ci-dessous, où E1 désigne l'étape 1, etc.

	E1	E2	E3	E4	Client
Domicile	$7$	$8$	$11$
E1		$14$
E2	$14$		$9$	$5$
E3		$9$		$7$	$12$
E4		$5$	$7$		$9$

Existe-t-il un trajet pour que cet artisan soit à l'heure ?

Nous allons utiliser l'algorithme de Dijkstra pour résoudre ce problème.
Construisons tout d'abord le graphe associé à la situation, avant de construire le tableau de l'algorithme.

0,0

D

E1

E2

E3

E4

C

7

9

8

14

11

5

7

9

12

D	E1	E2	E3	E4	C	On choisit :
$0$	$\infty$	$\infty$	$\infty$	$\infty$	$\infty$	$D(0)$
	$7_D$	$8_D$	$11_D$	$\infty$	$\infty$	$E1(7_D)$
		$8_D$	$11_D$	$\infty$	$\infty$	$E2(8_D)$
			$11_D$	$13_{E2}$	$\infty$	$E3(11_D)$
				$13_{E2}$	$23_{E3}$	$E_4(13_{E2})$
					$22_{E4}$	$C(22_{E4})$

Exercice 1 Déterminer le trajet minimal entre les sommets A et G du graphe ci-dessous.

0,0

A

B

C

D

E

F

G

H

40

50

60

110

50

120

120

55

45

40

90

80