Chapitre 2 problème de plus court chemin

CHAPITRE II: PROBLÈME DU PLUS COURT

CHEMIN

Université Blida 1Faculté des Sciences

Département d’InformatiqueMaster GSI (Génie des Systèmes Informatiques)

Semestre 1

Mme AROUSSI

2015-2016

Disponible sur https://sites.google.com/a/esi.dz/s-aroussi/

Introduction

Définition

Conditions (Optimalité/ Nécessaire)

Algorithmes de Résolution Algorithme de DIJKSTRA

Algorithme de BELLMAN

Algorithme de BELLMAN-FORD

Algorithme de FLOYD 2

PLAN DU CHAPITRE II

3

Le problème du Plus Court Chemin (PCC)

compte parmi les problèmes le plus classiques

de la théorie des graphes et les plus importants

dans leurs applications (les problèmes

d'optimisation de réseaux routiers ou

télécommunications, les problèmes de tournées,

….)

INTRODUCTION

4

Ce problème du Plus Court Chemin (PCC) peut être posé

de la façon suivante:

Etant donné un graphe orienté valué G (X,U,L), on

associe à chaque arc u(i,j) un nombre réel l(u) ou lij,

appelé la longueur ou le poids de l’arc, le PCC entre

deux sommets s (source ou origine) et d (destination)

du graphe consiste à déterminer, parmi tous les

chemins allant de s à d, un chemin, noté u*, dont la

longueur totale l(u*) = soit minimale

DÉFINITION

5

Condition Nécessaire: Le problème du plus court

chemin a une solution si et seulement s’il n'existe pas

dans le graphe de circuit de longueur strictement

négative pouvant être atteint à partir de l’origine (s).

Un circuit négatif est appelé circuit absorbant

INTRODUCTION

a

f

b

e

-3

-3

-1

c

d5

-510

2

6

Condition d’Optimalité: Les sous-chemins des plus

courts chemins sont des plus courts chemins.

INTRODUCTION

Exemples des arborescences des plus courts chemins dont l’origine

est aa

b

e

c

d

3

5

3

1 2

6

6

472

a

b

e

c

d

3

5

6

6

a

b

e

c

d

3

2 42

7

Selon les propriétés du graphe traité (orienté/non

orienté, avec/sans circuit ou longueurs

positives/quelconques) et selon le problème considéré

(recherche du plus court chemin d'un sommet vers

tous les autres, ou entre tous les couples de

sommets), il existe de nombreux algorithmes

permettant l'obtention d'une solution.

ALGORITHMES DE RÉSOLUTION

8

ALGORITHMES DE RÉSOLUTION

Algorithmes Type du PCC

Propriétés du graphe

Type de graphe Longueur

Dijkstra D’un sommet à tous les autressommets

Graphe orienté (et non orienté)

Longueur positives

Bellman Graphe orienté sans circuit (sommet d’origine doit être sans prédécesseur)

Longueur quelconque (nombre réel)

Bellman-Ford Graphe orienté

Floyd Entre tous les couples de sommets

Graphe orienté sans circuit absorbant

9

Cet algorithme permet de calculer le PCC d’un sommet «

s » à un sommet « d » ou d’un sommet « s » à tous les

autres sommets dans un graphe de longueur positive.

Soit (i) la valeur de chemin du sommet « s » vers le

sommet « i », ainsi, initialement : (s) = 0 et (x) =

pour tout sommet x ≠s

Soit M l’ensemble des sommets marqués, initialement

il est vide (M = )

ALGORITHME DE DIJKSTRA

10

Tant qu’il existe un sommet non marqué (M≠X) ou on

n’a pas arrivé au sommet destinataire (x ≠ d) faire:

1. Choisir un sommet non marqué, soit x (xX-M),

ayant le plus petit [(x) = min {(y) tq xX-M}]

2. Mettre à jours ses successeurs non encore marqués

comme suit: (y) = min ((y), (x)+lxy) tel que y+(x) (X-

M)

3. Marquer le sommet x [M = M {x}]


11

Exemple: Trouver PCC de a vers tous les autres sommets


(a) (b) (c) (d) (e)0 (init) 0

1 0 (*) 3 52 3(*) 9 53 9 11 5 (*)4 9(*)5 11(*)6 (fin) 0 3 9 11 5

a

b

e

c

d

3

5

3

1 2

6

6

472

12


Comment trouver le PCC chemin de a vers (b, e, c ou d)?

Pour chaque couple de sommet (i, j), on garde l’arc vérifiant la

relation suivante: u(i,j) = (j) - (i).


a

b

e

c

d

3

5

3

1 2

6

6

472

9

0

5

3

11

13


On peut trouver plusieurs arborescences:


a

b

e

c

d

3

5

6

6

9

0

5

3

11

a

b

e

c

d

3

2 42

9

0

5

3

11

14

Cet algorithme permet de calculer le PCC d’un sommet «

s » à un sommet « d » ou d’un sommet « s » à tous les

autres sommets dans un graphe orienté sans circuit de

longueur quelconque.

Soit (i) la valeur de chemin du sommet sans prédécesseur

« s » vers le sommet « i », ainsi, initialement : (s) = 0

Soit M l’ensemble des sommets marqués, initialement il

contient « s » (M = {s} )

ALGORITHME DE BELLMAN

15

Tant qu’il existe un sommet non marqué (M≠X) ou on

n’a pas arrivé au sommet destinataire (x ≠ d) faire:

1. Choisir un sommet non marqué, soit x (xX-M), dont

tous les prédécesseurs sont marqués [-(x) M]

2. Mettre à jours son poids comme suit: (x) = min

((y)+lyx) tel que y-(x)

3. Marquer le sommet x [M = M {x}]


16



(a) (b) (c) (d)0 (init) 0 (*) - - -1 2 (*)2 9(*)3 4(*)fin 0 2 9 4

a

c

b

d

10

2

-6

73

a

c

b

d

2

-6

7

0 2

9 4

17

Cet algorithme permet de calculer le PCC d’un sommet «s » à tous les autres sommets dans un graphe orienté delongueur quelconque et aussi de détecter la présence d’uncircuit absorbant.

Soit k(i) la valeur de chemin du sommet « s » vers lesommet « i » ne contenant pas plus de k arcs, ainsi,initialement : k = 0; k (s) = 0 et k(x) = pour x ≠s

Soit M l’ensemble des sommets dont le poids k (s) aété modifié à l’itération k, initialement il contient « s »(M = {s} )

ALGORITHME DE BELLMAN-FORD

18

Tant qu’il existe un sommet marqué (M≠) et k est

strictement inférieur à n (n présente le nombre des

sommets |X|) faire:

1. Incrémenter k

2. Initialiser l’ensemble NM à vide (NM contiendra les

sommet dont la marque k sera modifiée)


19

3. Pour tout sommet x de +(M) (i.e les successeurs des

sommets dont la marque a été modifié au cours de

l’itération k-1) faire:

a) Mettre à jours sa marque : k (x) = min (k-1 (x),

k -1(y) +lyx) tel que y-(x) M

b) Si sa marque a été modifiée (k (x) < k-1 (x) ) alors

ajouter x à l’ensemble NM (NM = NM {x})

4. Remplacer M par MN


20

En absence de circuit absorbant dans le graphe,

l’algorithme se termine nécessairement à l’issue de

l’itération n (k = n) car, au pire des cas, le PCC de s

vers tous les autre sommets est un chemin élémentaire

possédant (n-1) arcs.

Si une ou plusieurs marques sont modifiées à l’itération

n (+(M) ≠), cela signifie qu’il existe un circuit

absorbant.


21

Exemple 1: Trouver PCC de a vers tous les autres sommets


k k (a) k (b) k (c) k (d) k (e)0 (init) 0 (*)

1 0 3(*) 5(*)2 9(*) 11(*) 53 (fin) 0 3 9 11 5 4

a

b

e

c

d

3

5

3

1 2

6

6

472

22

Exemple 2: Trouver PCC de a vers tous les autres sommets


k k (a) k (b) k (c) k (d) k (e) k (f)0 (init) 0 (*)

1 10(*) 2(*)2 5(*) 7(*) -1(*)3 -4(*) 6(*)4 1(*) -2(*)5 3(*)6 2(*)

a

f

b

e

-3

-3

-1

c

d5

-510

2

23

Cet algorithme permet de calculer le PCC entre tous les

couples de sommets dans un graphe orienté sans circuit

absorbant de longueur quelconque.

Numéroter les sommets de 1 à n (|X| = n)

Soit la matrice A = {aij} de taille n x n définie initialement comme

suit:

ALGORITHME DE FLOYD

24

Cet algorithme permet de calculer le PCC de la façon

suivante:

A la première itération, on cherche le PCC entre

chaque couple (i, j) passant éventuellement par le

sommet 1 ;

A l'itération k (avec l > 1), on cherche le PCC entre

chaque couple (i, j) passant par des sommets d'indice

inférieur ou égal à k.

ALGORITHME DE FLOYD

25

Voici une description formelle de l'algorithme :

Pour tout sommet k (k allant de 1 à n)

Pour tout couple de sommet (i, j) calculer


j

i

k

k

26

Exemple: Trouver PCC entre tous les couples des sommets


a

c

b

d

6

2

5

-1-2-4 5

SOURCES DE CE COURS

Lucas Letocart, Cours d’Algorithmique de graphes, Institut Galilée,

Université Paris 13, Disponible sur www-galilee.univ-

paris13.fr/fichiers/Cours_Algo_Graphes.pdf

Laurent Canet, Algorithmique, graphes et programmation

dynamique, Notes de Cours & Rapport de Travaux Pratiques, 2003

Aroussi Sana, Notes des Travaux Dirigés de Recherche

Opérationnelle, Ecole nationale Supérieure d’Informatique (ESI),

2013. 27

Education

Chapitre 2 problème de plus court chemin