Algorithme de Dijkstra

Td Algorithme module Informatique et Programmation CP1

Ensa Marrakech

CHAPITRE 3-2 Graphe oriente (Suite )

Algorithme de Dijkstra

Edgser Wybe Dijkstra (1930-2002) a propos en 1959 un algorithme qui permet de calculer le plus court chemin entre un sommet particulier et tous les autres. Le rsultat est une arborescence.

Numrotons les sommets du graphe G = (V,E) de 1 n. Supposons que l'on s'intresse aux chemins partant du sommet 1.On construit un vecteur = ((1); (2); ...; (n)) ayant n composantes tel que (j) soit gal la longueur du plus court chemin allant de 1 au sommet j. On initialise ce vecteur c1,j, c'est--dire la premire ligne de la matrice des cots du graphe, dfinie comme indiqu ci-dessous:

o (i,j) est le poids (la longueur) de l'arc (i,j). Les cij doivent tre strictement positifs.On construit un autre vecteur p pour mmoriser le chemin pour aller du sommet 1 au sommet voulu. La valeur p(i) donne le sommet qui prcde i dans le chemin.On considre ensuite deux ensembles de sommets, S initialis {1} et T initialis {2, 3, ..., n}. chaque pas de l'algorithme, on ajoute S un sommet jusqu' ce que S = V de telle sorte que le vecteur donne chaque tape le cot minimal des chemins de 1 aux sommets de S.

Description de l'algorithme de Dijkstra

On suppose ici que le sommet de dpart (qui sera la racine de l'arborescence) est le sommet 1. Notons qu'on peut toujours renumroter les sommets pour que ce soit le cas.

Initialisations(j) = c1,j et p(j) = NIL, pour 1 j nPour 2 j n faireSi c1,j < alors p(j) = 1.S = {1} ; T = {2, 3, ..., n}.

ItrationsTant que T n'est pas vide faireChoisir i dans T tel que (i) est minimumRetirer i de T et l'ajouter SPour chaque successeur j de i, avec j dans T, faireSi (j) > (i) + (i,j) alors(j) = (i) + (i,j)p(j) = i

Exemple

InitialisationsS = {1} ; T = {2, 3, 4, 5} ; = (0, 15, , , 4); p = (NIL, 1, NIL, NIL, 1) Graphe de dpart

Arborescence donnant les plus courts chemins du sommet 1 tous les autres.

1re itrationi = 5 car (5) = min(15, , , 4) = 4;S = {1, 5}; T = {2, 3, 4};les successeurs de 5 dans T sont 3 et 4;(3) prend la nouvelle valeur min(; (5) + (5; 3)) = min(; 4 + 7) = 11; p(3) = 5;(4) prend la nouvelle valeur min(; (5) + (5; 4)) = 9; p(4) = 5;d'o les nouveaux vecteurs = (0, 15, 11, 9, 4) et p = (NIL, 1, 5, 5, 1)

2e itrationi = 4; (4) = 9;S = {1, 5, 4}; T = {2, 3};le seul successeur de 4 dans T est 2;(2) prend la nouvelle valeur min(; (4) + (4; 2)) = min(15; 9 + 3) = 12; p(2) = 4;d'o les nouveaux vecteurs = (0, 12, 11, 9, 4) et p = (NIL, 4, 5, 5, 1)

3e itrationi = 3; (3) = 11;S = {1, 5, 4, 3}; T = {2};le seul successeur de 3 dans T est 2;(2) garde sa valeur car min(12; (3) + (3; 2)) = min(12; 11 + 3) = 12;d'o les vecteurs inchangs = (0, 12, 11, 9, 4) et p = (NIL, 4, 5, 5, 1)

4e itrationi = 2; (2) = 12;S = {1, 5, 4, 3, 2}; T={}; FIN. = (0, 12, 11, 9, 4);p = (NIL, 4, 5, 5, 1).

Le chemin minimal de 1 4 par exemple est de cot 9. C'est le chemin 1-5-4, car p(4) = 5 et p(5) = 1.

EXERCICES

Exercice 1

Expliquez pourquoi des arcs avec des poids ngatifs pourraient poser problme dans la recherche d'un plus court chemin dans un graphe.

Exercice 2

Appliquez l'algorithme de Dijkstra au graphe de l'exemple ci-dessous pour trouver tous les plus courts chemins en partant du sommet 1