Arbre

Couvrant
Pr. Cheikh Noufissa
[Link]@[Link]
Pr N. CHEIKH 1
 Algorithmes d’Arbre Couvrant

• Algorithme de Kruskal

• Algorithme de Prim

Pr N. CHEIKH 2
 Définition Arbre Couvrant

Un arbre couvrant d’un graphe G(V, E) est un graphe partiel, sans cycle (acyclique)

Pr N. CHEIKH 3
 Définition graphe pondéré

• Un graphe pondéré G( V, E, ꙍ), est un graphe ou un entier positif est affecté

à chaque arête.
• On appelle cet entier poids de l’arête

Pr N. CHEIKH 4
 Définition graphe pondéré

• Le poids ou coût d’un graphe est la somme des poids des arêtes du graphe
• On le note ꙍ (G)

ꙍ (G) = 79

Pr N. CHEIKH 5
Arbre Couvrant de Poids Minimum (ACPM)
Minimum Spanning Tree (MST)

Pr N. CHEIKH 6
Arbre Couvrant de Poids Minimum (ACPM)
Minimum Spanning Tree (MST)

Exemple:

Pr N. CHEIKH 7
Arbre Couvrant de Poids Minimum (ACPM)
Minimum Spanning Tree (MST)

Exemple:

ꙍ(G’) = 37

Pr N. CHEIKH 8
Application 1

Pr N. CHEIKH 9
 Application 1

Solution 1

Pr N. CHEIKH 10
 Application 1

Solution 2

ꙍ(G’) = 43

Pr N. CHEIKH 11
 Application 1

Solution 3

ꙍ(G’) = 40

Pr N. CHEIKH 12
Algorithme de Kruskal

Pr N. CHEIKH 13
Algorithme de Kruskal

Pr N. CHEIKH 14
Algorithme de Kruskal

Pr N. CHEIKH 15
Algorithme de Kruskal

Pr N. CHEIKH 16
Algorithme de Kruskal

Pr N. CHEIKH 17
Algorithme de Kruskal

Pr N. CHEIKH 18
Algorithme de Kruskal

Pr N. CHEIKH 19
Algorithme de Kruskal

Pr N. CHEIKH 20
Algorithme de Kruskal

Pr N. CHEIKH 21
Algorithme de Kruskal

Pr N. CHEIKH 22
Algorithme de Kruskal

Pr N. CHEIKH 23
 Algorithme de Kruskal

ꙍ(G’) = 40

Pr N. CHEIKH 24
Algorithme de Prim

Pr N. CHEIKH 25
Algorithme de Prim

Pr N. CHEIKH 26
Algorithme de Prim

Pr N. CHEIKH 27
Algorithme de Prim

Pr N. CHEIKH 28
Algorithme de Prim

Pr N. CHEIKH 29
Algorithme de Prim

Pr N. CHEIKH 30
Algorithme de Prim

Pr N. CHEIKH 31
Algorithme de Prim

Pr N. CHEIKH 32
Algorithme de Prim

Pr N. CHEIKH 33
Algorithme de Prim

Pr N. CHEIKH 34
Algorithme de Prim

Pr N. CHEIKH 35
Algorithme de Prim

Pr N. CHEIKH 36
 Application

Trouver L’ACPM en appliquant l’algorithme de Kruskal ou l’algorithme de Prim

Pr N. CHEIKH 37
 Application - Solution

ꙍ(G’) = 400

Pr N. CHEIKH 38
Pr N. CHEIKH 39
 Les Problèmes du
Plus Court Chemin (PCC)

Théorie des graphes

 Les algorithmes de PCC

• Algorithme de Ford

• Algorithme de Dijkstra

• Algorithme de Bellman-Ford

Pr N. CHEIKH 41
Recherche des chemins de longueur extrémale

Problème: comment chercher le ou les chemins de longueur extrémale (minimale

ou maximale) partant du sommet n°1 vers un sommet donné.

Pr N. CHEIKH 42
Recherche des chemins de longueur extrémale

Pr N. CHEIKH 43
 Partitionnement des sommets du graphe
par niveau
Exemple :

Pr N. CHEIKH 44
 Partitionnement des sommets du graphe
par niveau

Tous les éléments d’un même niveau n’ont pas d’ancêtres dans le niveau qui suit, ni
de descendants dans le niveau qui précède.

Les éléments du premier niveau n’ont pas d’ancêtres et ceux du dernier niveau
n’ont pas de descendants.

L’ordre des sommets d’un même niveau est indifférent i.e. les sommets d’un même
niveau ne sont pas reliés entre eux par des arcs.

Une décomposition par niveaux existe toujours mais elle n’est pas nécessairement unique
Pr N. CHEIKH 45
 Partitionnement des sommets du graphe
par niveau
Procédé :

❑ On détermine d’abord les sommets qui n’ont pas d’antécédents

❑ On constate que le sommet 5 n’admet aucun antécédent.

❑ Le sommet 5 forme le niveau I.

❑ Pour déterminez le niveau II, il faut chercher tous les

sommets dont le seul ancêtre est 5
❑ Le sommet 2 n’a pas d’autres ancêtres que le sommet 5.
❑ Le sommet 2 forme le niveau 2.

Comme on peut le constater, pour obtenir les sommets d’un niveau, il suffit d’enlever au
vecteur précédent les lignes associées aux sommets du niveau précédent.
Pr N. CHEIKH 46
Tableau de niveaux:

Sommets Antécédents N1 N2 N3 N4 N5 N6 N7
1 5, 6, 2

2 5

3 6

4 6, 7

5 _ 5

6 2, 5

7 2, 3, 5

8 1, 4, 5

Pr N. CHEIKH 47
Tableau de niveaux:

Sommets Antécédents N1 N2 N3 N4 N5 N6 N7
1 5, 6, 2 1

2 5
3 6 2 3

4 6, 7 4
5 _ 5
6 2, 5 6

7 2, 3, 5 7
8 1, 4, 5 8

Pr N. CHEIKH 48
Le graphe peut alors se mettre sous la forme :

Pr N. CHEIKH 49
Algorithme de Ford

Pr N. CHEIKH 50
Algorithme de FORD

Pr N. CHEIKH 51
Algorithme de FORD

Pr N. CHEIKH 52
 Algorithme de FORD

• Distance minimale entre x0 et x5 est: 10

• Le chemin le plus court est: x0, x1, x3, x4, x5
Pr N. CHEIKH 53
Application 2

Pr N. CHEIKH 54
 Application 2

La distance minmale est 48

Le chemin le plus court est:

Pr N. CHEIKH 55
 Application

B D F

A H

C E G

Trouver le plus court chemin en appliquant l’algorithme de Ford

Pr N. CHEIKH 56
 Application
𝒕𝟏 =5 𝒕𝟑 = 𝟏𝟏 𝒕𝟓 = 𝟏𝟐
B D F
𝒕𝟎 = 𝟎
A H 𝒕𝟕 = 𝟏𝟕

C E G
𝒕𝟐 =10 𝒕𝟒 = 𝟏𝟏 𝒕𝟔 =15

Le PCC entre A et H est ACDFGH de poids 17

Pr N. CHEIKH 57
Algorithme de Dijkstra

Pr N. CHEIKH 58
 Algorithme de Dijkstra

Etape 1: Initialisation
• On prends un sommet du départ (sommet a dans notre cas)
• On attribue à toutes les distances de a vers les autres sommets ∞

Pr N. CHEIKH 59
 Algorithme de Dijkstra

Etape 2: Traitement du sommet a

Pr N. CHEIKH 60
 Algorithme de Dijkstra

Etape 3: Traitement du sommet le plus proche de a

e est le sommet lePr [Link]

CHEIKH
proche de a 61
 Algorithme de Dijkstra

Etape 4: Traitement du sommet le plus proche de e

d est le sommet le plus proche de e

Pr N. CHEIKH 62
 Algorithme de Dijkstra

Etape 5: Traitement du sommet le plus proche de d

b est le sommet le plus proche de d

Tous les sommets ont été traitésPr N. CHEIKH fin de l’algorithme 63

 Algorithme de Dijkstra

Solution finale

Pr N. CHEIKH 64
Algorithme de Dijkstra

Pr N. CHEIKH 65
Algorithme de Dijkstra

Pr N. CHEIKH 66
Algorithme de Dijkstra

Pr N. CHEIKH 67
Algorithme de Dijkstra

Pr N. CHEIKH 68
Algorithme de Dijkstra

Pr N. CHEIKH 69
Algorithme de Dijkstra

Pr N. CHEIKH 70
Algorithme de Dijkstra

Pr N. CHEIKH 71
Algorithme de Dijkstra

Pr N. CHEIKH 72
Algorithme de Dijkstra

Pr N. CHEIKH 73
Trouver le plus court chemin d’origine E en appliquant l’algorithme de Dijkstra

Pr N. CHEIKH 74
 Problème avec l’algorithme de Dijkstra

• Problème 1:

Dijkstra ne fonctionne pas toujours avec un arc portant un poids négatif.

Exemple

Pr N. CHEIKH 75
 Problème avec l’algorithme de Dijkstra

• Problème 2:

• L’algorithme de Dijkstra n’est pas très “orienté cible” : dans le cas où

un chemin particulier de la source vers la destination doit être trouvé,
l’algorithme n’est pas très performant.

Pr N. CHEIKH 76
 Problème avec l’algorithme de Dijkstra

• Problème 2:

Pr N. CHEIKH 77
 Problème avec l’algorithme de Dijkstra

• Problème 2:

Pr N. CHEIKH 78
 Problème avec l’algorithme de Dijkstra

• Problème 2:

Pr N. CHEIKH 79
 Problème avec l’algorithme de Dijkstra

• Problème 2:

Pr N. CHEIKH 80
 Problème avec l’algorithme de Dijkstra

• Problème 2:
21

28

Pr N. CHEIKH 81
 Problème avec l’algorithme de Dijkstra

• Problème 2:
21

28

24

Pr N. CHEIKH 82
 Problème avec l’algorithme de Dijkstra

• Problème 2:
21

22
28

24

Pr N. CHEIKH 83
 Problème avec l’algorithme de Dijkstra
38
• Problème 2:
21

22
28

24

Pr N. CHEIKH 84
Algorithme de Bellman Ford

Pr N. CHEIKH 85
 Introduction
❑L‘algorithme de Bellman-Ford résout le problème de recherche de plus court chemin
depuis une source unique, mais en autorisant des arcs portant des poids négatifs.

❑Il permet de détecter l‘existence d‘un circuit absorbant, c‘est-à-dire de poids total
strictement négatif, accessible depuis le sommet source.

❑Cependant, si le graphe contient un circuit absorbant, il n‘existe pas de solution.

❑L‘algorithme de Bellman-Ford utilise également la méthode de relaxation

Pr N. CHEIKH 86
 Circuit absorbant
• Un circuit absorbant est un circuit ayant un poids total négatif (ie : un cycle qui,
dans le contexte d’un plus cours chemin, nous imposerait de rester dans ce cycle
infiniment pour réduire le poids infiniment.)

Pr N. CHEIKH 87
 Algorithme de Bellman-Ford
On a 6 sommets --˃ 5 itérations

S A B C D E
Itération 0 0 ∞ ∞ ∞ ∞ ∞
Itération 1
Itération 2
Itération 3
Itération 4
Itération 5

Pr N. CHEIKH 88
 Algorithme de Bellman-Ford
On a 6 sommets --˃ 5 itérations

S A B C D E
Itération 0 0 ∞ ∞ ∞ ∞ ∞
Itération 1 0 10 8

Itération 2
Itération 3
Itération 4
Itération 5

Pr N. CHEIKH 89
 Algorithme de Bellman-Ford
On a 6 sommets --˃ 5 itérations

S A B C D E
Itération 0 0 ∞ ∞ ∞ ∞ ∞
Itération 1 0 10 10 12 9 8
Itération 2
Itération 3
Itération 4
Itération 5

Pr N. CHEIKH 90
 Algorithme de Bellman-Ford
On a 6 sommets --˃ 5 itérations

S A B C D E
Itération 0 0 ∞ ∞ ∞ ∞ ∞
Itération 1 0 10 10 12 9 8
Itération 2 0 5 10 8 9 8
Itération 3
Itération 4
Itération 5

D améliore les chemins vers A et vers C

Pr N. CHEIKH 91
 Algorithme de Bellman-Ford
On a 6 sommets --˃ 5 itérations

S A B C D E
Itération 0 0 ∞ ∞ ∞ ∞ ∞
Itération 1 0 10 10 12 9 8
Itération 2 0 5 10 8 9 8

Itération 3 0 5 5 7 9 8

Itération 4
Itération 5

A améliore le chemin vers C

C améliore le chemin
Pr N. CHEIKHvers B 92
 Algorithme de Bellman-Ford
On a 6 sommets --˃ 5 itérations

S A B C D E
Itération 0 0 ∞ ∞ ∞ ∞ ∞
Itération 1 0 10 10 12 9 8
Itération 2 0 5 10 8 9 8

Itération 3 0 5 5 7 9 8
Itération 4 0 5 5 7 9 8
Itération 5

Pr N. CHEIKH 93
 Algorithme de Bellman-Ford
On a 6 sommets --˃ 5 itérations

S A B C D E
Itération 0 0 ∞ ∞ ∞ ∞ ∞
Itération 1 0 10 10 12 9 8
Itération 2 0 5 10 8 9 8

Itération 3 0 5 5 7 9 8
Itération 4 0 5 5 7 9 8
Itération 5 0 5 5 7 9 8

Pr N. CHEIKH 94
 Application 2

Déterminer le PCC de s à p en
appliquant l’algorithme Bellman-Ford.

Pr N. CHEIKH 95
Algorithme de Bellman-Ford

s 1 2 3 4 p
Iter 0 0 ∞ ∞ ∞ ∞ ∞
Iter 1 0 4 19 -2 0 17
Iter 2 0 4 19 -2 0 17
Iter 3 0 4 19 -2 0 17
Iter 4 0 4 19 -2 0 17
Iter 5 0 4 19 -2 0 17

Pr N. CHEIKH 96
Algorithme de Bellman-Ford

Tableau des prédécesseurs

Pr N. CHEIKH 97
 Algorithme de Bellman-Ford

• En reprenant le tableau des prédécesseurs à l’envers, le PCC de s à p est :

• La somme des poids des arcs de ce sommet est de 17.

Pr N. CHEIKH 98
 Application 3

Déterminer le PCC de 1 à 7 en appliquant l’algorithme Bellman-Ford.

Pr N. CHEIKH 99
 1 2 3 4 5 6 7
Itération 0 0 ∞ ∞ ∞ ∞ ∞ ∞
Itération 1 0 3 3 5 5 4 7
Itération 2 0 1 3 5 2 4 5
Itération 3 0 1 3 5 0 4 3
Itération 4 0 1 3 5 0 4 3
Itération 5 0 1 3 5 0 4 3
Itération 6 0 1 3 5 0 4 3
Pr N. CHEIKH 100
 1 2 3 4 5 6 7
Itération 0 0 ∞ ∞ ∞ ∞ ∞ ∞
Itération 1 0 3 3 5 5 4 7
Itération 2 0 1 3 5 2 4 5
Itération 3 0 1 3 5 0 4 3
Itération 4 0 1 3 5 0 4 3
Itération 5 0 1 3 5 0 4 3
Itération 6 0 1 3 5 0 4 3
Pr N. CHEIKH 101
Cas particulier – Détection du Circuit absorbant

Pr N. CHEIKH 102
 S A B C D
Itération 0 0 ∞ ∞ ∞ ∞

Itération 1 0 3 (S) 6 (D) 4 (A) 9 (C)

Itération 2 0 3 (S) 4 (D) 4 (A) 7 (B)
Itération 3 0 3 (S) 2 (D) 4 (A) 5 (B)
Itération 4 0 3 (S) 0 (D) 4 (A) 3 (B)

Pr N. CHEIKH 103
 S A B C D
Itération 0 0 ∞ ∞ ∞ ∞

Itération 1 0 3 (S) 6 (D) 4 (A) 9 (C)

Itération 2 0 3 (S) 4 (D) 4 (A) 7 (B)
Itération 3 0 3 (S) 2 (D) 4 (A) 5 (B)
Itération 4 0 3 (S) 0 (D) 4 (A) 3 (B)

Pr N. CHEIKH 104
 S A B C D
Itération 0 0 ∞ ∞ ∞ ∞

Itération 1 0 3 (S) 6 (D) 4 (A) 9 (C)

Itération 2 0 3 (S) 4 (D) 4 (A) 7 (B)
Itération 3 0 3 (S) 2 (D) 4 (A) 5 (B)
Itération 4 0 3 (S) 0 (D) 4 (A) 3 (B)

Pr N. CHEIKH 105
 S A B C D
Itération 0 0 ∞ ∞ ∞ ∞

Itération 1 0 3 (S) 6 (D) 4 (A) 9 (C)

Itération 2 0 3 (S) 4 (D) 4 (A) 7 (B)
Itération 3 0 3 (S) 2 (D) 4 (A) 5 (B)
Itération 4 0 3 (S) 0 (D) 4 (A) 3 (B)

Pr N. CHEIKH 106
 S A B C D
Itération 0 0 ∞ ∞ ∞ ∞

Itération 1 0 3 (S) 6 (D) 4 (A) 9 (C)

Itération 2 0 3 (S) 4 (D) 4 (A) 7 (B)
Itération 3 0 3 (S) 2 (D) 4 (A) 5 (B)
Itération 4 0 3 (S) 0 (D) 4 (A) 3 (B)

Circuit de coût négatif: le cycle (bdb) a une valeur égale à -2 ˂0

Réduction encore possible après la dernière itération
le plus court chemin entre s et d est indéterminé

Pr N. CHEIKH 107
Une application importante des algorithmes de plus courts chemins :

Routage dans les réseaux de communications

Déterminer le chemin le plus efficace pour router les messages jusqu’`a leurs destinations.

• Les longueurs (délais) sont positives mais l’algorithme de Dijkstra a l’inconvénient de

fonctionner globalement (choix de la marque minimal).
• Au contraire, l’algorithme de Bellman-Ford est plutôt local. chaque nœud a besoin
seulement de connaître les marques de ses voisins.
Pr N. CHEIKH 108
Conclusion

Pr N. CHEIKH 109
 Quel algorithme choisir pour un PCC

Graphe avec circuit?

Non Oui

Algorithme de Ford poids des arcs/arêtes positives?

Non Oui

Algorithme de Bellman- Ford Algorithme de Dijkstra

Pr N. CHEIKH 110