Algorithmique

Notes de cours

Université Paris Diderot

Copyright c 2015 Sophie Laplante (Professeur), notes de Maxime Gourgoulhon (étudiant)

P UBLISHED BY CC

INFORMATIQUE . UNIV- PARIS - DIDEROT. FR

Licensed under the Creative Commons Attribution-NonCommercial 3.0 Unported License (the
“License”). You may not use this file except in compliance with the License. You may obtain a
copy of the License at [Link] Unless required
by applicable law or agreed to in writing, software distributed under the License is distributed on an
“AS IS ” BASIS , WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and limitations under the License.

First printing, November 2015

 Table des matières

I Union-Find
1 Graphes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.1 Définition 9
1.2 Représentations 9
1.2.1 Matrice d’adjacence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.2.2 Liste d’adjacence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.3 Chemins 10
1.4 Cycle 10
1.5 Connexe 10
1.6 Arbres 10
1.7 Arbre couvrants 10
1.8 Graphes valués 11
1.9 Algorithme de Kruskal (1956) 11

2 Cycles et composantes connexes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

2.1 Problèmes 13
2.2 Application : Kruskal 13

3 L’algorithme : Union-Find . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
3.1 Définition 15
3.2 Exemple 15
3.3 Applications 15
3.4 Idée de l’algorithme 16
3.5 Retour sur Kruskal 16
3.6 Implémentation en Python 16
3.7 Complexité 17
3.8 UNION : Maîtriser la hauteur des arbres 17
3.9 FIND : Compresser les chemins 17

II Parcours d’arbres

4 Arbres binaires de recherche ABR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

4.1 Complexité 21
4.2 Arbres binaires de recherche 21
4.3 Recherche dans un ABR 22
4.3.1 Preuve par récurrence sur |A| . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
4.4 Insertion dans un ABR 23
4.4.1 Algorithme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
4.4.2 Coût moyen d’insertion de n éléments dans un ABR vide . . . . . . . . . . . . . . . . 23

III Parcours de graphes

5 Parcours d’arbres k-aire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

5.1 Structure de donnée utilisée 27
5.2 Parcours en largeur des arbres 28
5.3 Propriétés du parcours en largeur 28
5.4 Parcours en profondeur des arbres 29
5.5 Propriétés du parcours en profondeur des arbres 29

6 Parcours de graphes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
6.1 Représentation des graphes (non orientés) 31
6.2 Parcours en largeur des graphes 31
6.3 Parcours en profondeur des graphes 33
6.3.1 Version récursive . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
6.3.2 Version itérative . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

IV Algorithmes de graphes

7 Algorithme de Kruskal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
7.1 Implémentation de l’algorithme de Krukal 37
7.2 Correction de l’algorithme de Kruskal 37
7.2.1 Lemme d’optimalité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
8 Algorithme de Prim . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
8.1 Implémentation de l’algorithme de Prim (version optimisée) 39
8.2 Complexité de l’algorithme de Prim 40

9 Les plus cours chemins : Dijkstra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

9.1 Algorithme de Dijkstra 41
9.2 Preuve de l’algorithme de Dijkstra 42

10 Algorithme de Bellman-Ford . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
10.1 Idée 45
10.2 Implémentation en Python 46
10.3 Preuve 46

11 All pairs shortest paths . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47

11.1 Dijkstra, plusieurs fois 47
11.2 Modification de Bellman-Ford 47
11.3 En doublant la longueur des chemins à chaque itération 48
11.4 Algorithme de Floyd-Warshall 49

12 Cycles négatifs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
12.1 Algorithme pour détecter les cycles négatifs 51

Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
I
Union-Find

1 Graphes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.1 Définition
1.2 Représentations
1.3 Chemins
1.4 Cycle
1.5 Connexe
1.6 Arbres
1.7 Arbre couvrants
1.8 Graphes valués
1.9 Algorithme de Kruskal (1956)

2 Cycles et composantes connexes . . . . 13

2.1 Problèmes
2.2 Application : Kruskal

3 L’algorithme : Union-Find . . . . . . . . . . . . . 15
3.1 Définition
3.2 Exemple
3.3 Applications
3.4 Idée de l’algorithme
3.5 Retour sur Kruskal
3.6 Implémentation en Python
3.7 Complexité
3.8 UNION : Maîtriser la hauteur des arbres
3.9 FIND : Compresser les chemins
 1. Graphes

1.1 Définition
Définition 1.1.1 — Graphe. Un graphe est constitué d’un ensemble de sommets S d’un en-
semble d’arêtes A ⊆ S × S reliant les sommets. Les arêtes sont orientées (flèche) ou non orientées
(segment).

Notation 1.1. On note un graphe G = (S, A) en français, G = (V, E) en anglais.

F IGURE 1.1 – Graphe non orienté F IGURE 1.2 – Graphe orienté

Les sommets peuvent représenter des villes, des stations de métro, des sites sur des cartes
géographiques, etc. Les arêtes peuvent symboliser des routes, des câbles, des liens, etc. Un graphe
peut ainsi représenter des cartes géographiques, le web, les réseaux sociaux, des modèles 3D
(animations), modèles physiques d’interactions...

1.2 Représentations

1 5

2 3 6

F IGURE 1.3 – Graphe non orienté

 10 Chapitre 1. Graphes

1 2 3 4 5 6
1 2 3
1 0 1 1 0 0 0
2 1 3 4
2 1 0 1 1 0 0
3 1 2 4
3 1 1 0 1 0 0
4 2 3
4 0 1 1 0 0 0
5 6
5 0 0 0 0 0 1
6 5
6 0 0 0 0 1 0

F IGURE 1.5 – Liste d’adjacence du graphe 1.3

F IGURE 1.4 – Matrice d’adjacence du graphe 1.3

1.2.1 Matrice d’adjacence

Une matrice d’adjacence pour un graphe G à n sommets est une matrice de dimension n × n
dont où l’élément à la position i, j vaut 1 s’il existe une arête reliant le sommet i au sommet j, 0
sinon.

1.2.2 Liste d’adjacence

Une liste d’adjacence est la liste des voisins de chaque sommets. C’est une représentation
relativement compacte lorsqu’il y a peu d’arêtes.

1.3 Chemins
Définition 1.3.1 — Chemin. Un chemin de longueur k de u à v dans un graphe G = (S, A) est
une suite de sommets u0 , u1 , ... uk telle que u0 = u, uk = v et on ne passe que par des arêtes de
G. ∀i ∈ J0, kK ∈ A

Définition 1.3.2 — Chemin simple. Un chemin simple est un chemin qui ne passe pas 2 fois
par le même sommet.

Exemples sur la figure 1.3 :

— 1, 3, 2, 4 est une chemin de longueur 3, de 1 à 4.
— 1, 4, 5 n’est pas un chemin.

1.4 Cycle
Définition 1.4.1 — Cycles. Pour u ∈ S, un cycle est un chemin de longueur supérieure ou égale
à 3, de u à u, qui ne passe pas deux fois par le même sommet. Le graphe de la figure 1.3 possède
des cycles.

1.5 Connexe
Définition 1.5.1 — Connexe. Un graphe est connexe si ∀u, v ∈ S il existe un chemin de u à v
dans G. Le graphe de la figure 1.3 n’est pas connexe. Le graphe de la figure 1.6 est connexe.

1.6 Arbres
Définition 1.6.1 — Arbre. Un arbre est un graphe connexe sans cycle.

1.7 Arbre couvrants

 1.8 Graphes valués 11

F IGURE 1.6 – Arbre

Définition 1.7.1 — Arbre couvrant. Un arbre T = (S, A0 ) couvre un graphe G = (S, A) si

A0 ⊆ A.

Un graphe à n sommets peut admettre jusqu’à nn−1 arbres couvrants.

1.8 Graphes valués

Définition 1.8.1 — Graphe valué. Un graphe est valué (ou pondéré) lorsqu’on y associe une
fonction de coût sur les arêtes : w : S × S → R+

1 4
2
4 1

F IGURE 1.7 – Graphe non orienté

1.9 Algorithme de Kruskal (1956)

L’algorithme de Kruskal (1956) permet de trouver un arbre couvrant minimal dans un graphe
valué G = (S, A) , w : S × S → R+ .
1. Trier les arêtes par ordre de coût.
2. Parcourir toutes les arêtes (u, v) dans cet ordre. Si (u, v) ne forme pas de cycle, l’ajouter à
l’arbre.

À ne pas confondre
Un problème décrit sur chaque donnée quel est le résultat attendu. ex : tri, recherche.
La structure de données décrit comment les données sont organisées et comment on y accède.
Un algorithme décrit le déroulement des étapes permettant de résoudre un problème.
Un programme (ou implémentation) est un choix des structures de données, des librairies,
du langage, de l’interface...
12 Chapitre 1. Graphes

Exercices
Exercice 1 : Ordres de grandeur
Donner les relations (o, O, θ ) entre les fonctions f et g suivantes :
1. f (n) = 2n et g(n) = 5n + 1 ;
2. f (n) = n2 et g(n) = n3 ;
3. f (n) = n2 et g(n) = 2n2 + 3n + 5 ;
4. f (n) = 8(log n)2 et g(n) = n − 2 ;
5. f (n) = log(n2 ) et g(n) = log n ;
6. f (n) = 2n et g(n) = n10 ;
7. f (n) = 2n+1 et g(n) = 2n ;
8. f (n) = 22n et g(n) = 2n .

Exercice 2 : Représentation des arbres

Un arbre (pas forcément binaire) peut être représenté de deux façons :
— par les prédécesseurs : chaque nœud contient un pointeur vers son père.
— par liste d’adjacence : chaque nœud contient la liste de tous ses fils.
1. Dessiner un arbre à 8 sommets et donner les deux façons de le représenter.
2. Proposer un algorithme qui transforme un arbre donné par liste d’adjacence en un arbre
donné par prédécesseurs. Évaluer sa complexité.
3. Donner un algorithme qui transforme un arbre donné par prédécesseurs en un arbre donné
par liste d’adjacence. Évaluer sa complexité.
Solution : [Link]
files/[Link]
 2. Cycles et composantes connexes

2.1 Problèmes
Problème 2.1 Soit G = (S, A) et u, v ∈ S.
Répondre V RAI si il existe un chemin de u à v dans G, FAUX sinon.
Problème 2.2 Soit G = (S, A) et u, v ∈ S.
Est-ce qu’ajouter (u, v) à A crée un nouveau cycle ?
Proposition 2.1.1 Problème 2.1 ⇔ Problème 2.2
Si il existe un chemin de u à v : u = u1 , u2 , ...uk = v (qui ne passe pas 2 fois par le même
sommet) alors il existe un cycle si on ajoute u, v.
Dans l’autre sens, si ajouter (u, v) crée un nouveau cycle, alors il existe un chemin. En effet, si
le morceau cycle passe par u, v1 , ...vk , u alors G contient le chemin u, vk , ..., v1 , v.
Définition 2.1.1 Une composante connexe d’un graphe G = (S, A) est un sous-ensemble de
sommets S0 ⊆ S maximal tel que ∀u, v ∈ S0 , il existe un chemin de u à v dans G.

Problème 2.3 Soient G = (S, A) et u, v ∈ S, u et v sont-ils dans la même composante connexe ?

2.2 Application : Kruskal

A
1 2
B 4 C
4 1
D

Trier les arêtes : (A, B)(C, D)(A,C)(B,C)(B, D)

14 Chapitre 2. Cycles et composantes connexes

Ajouter dans l’ordre sans créer de cycle :

1. Ajouter (A, B), 3 composantes connexes.

B C

2. Ajouter (C, D), 2 composantes connexes.

B C

3. Ajouter (A,C) ? Ok, A et C ne sont pas dans la même composante connexe.

B C

4. Ajouter (B,C). Non.

Objectif : trouver un algorithme performant pour résoudre le problème 2.1.
 3. L’algorithme : Union-Find

3.1 Définition
On démarre avec des éléments d’un univers U (ici les sommets d’un graphe). On admet 2
opérations :
— UNION(u, v) : associe u et v (ici, on ajoute une arête)
— FIND(u, v) : permet de savoir si u et v sont associés, transitive (ici, si il existe un chemin de
u à v)

3.2 Exemple

Algorithm 1 Algorithme de Kruskal

for (u, v) in A (par ordre croisant d’étiquette) do
if not FIND(u, v) then
UNION(u, v)
else
end
end if
end for

3.3 Applications
— Segmentation d’image (combien de formes dans une image).
— Construction de labyrinthes.
— Kruskal, arbre couvrant minimal.
— Détection de cycles.
 16 Chapitre 3. L’algorithme : Union-Find

3.4 Idée de l’algorithme

Chaque élément connait son "chef".
On note Id[u] le chef de u.
Pour savoir si u et v sont associés, on note la "hiérarchie" de chef en chef. Si u et v ont le même
"PDG", alors u et v sont associés.
Pour associer u et v : UNION(u, v) = le chef du "PDG" de u devient le "PDG" de v.

w E

v D

u C

F IGURE 3.1 – UNION(u, B)

3.5 Retour sur Kruskal

On teste successivement les arêtes avec FIND , tant que la fonction renvoie FAUX on utilise
UNION, sinon on a fini.

3.6 Implémentation en Python

La classe UF en Python :
1 class UF :
2 def __init__ ( self , U ):
3 self . Id = {}
4 for x in U :
5 self . Id [ x ] = x
6 def root1 ( self , u ):
7 while self . Id [ u ] != u :
8 u = self . Id [ u ]
9 return u
10 def find1 ( self , u , v ):
11 return self . root1 ( u ) == self . root1 ( v )
12 def union1 ( self , u , v ):
13 if not self . find1 (u , v ):
14 chefu = self . root1 ( u )
15 chefv = self . root1 ( v )
16 self . Id [ chefu ] = chefv
 3.7 Complexité 17

3.7 Complexité
— root1 : O(hauteur de l’arbre)
— find1 : 2 × hauteur + 1
— union1 : 4 × hauteur + 1

3.8 UNION : Maîtriser la hauteur des arbres

Pour améliorer la complexité on cherche à maîtriser la hauteur des arbres.
Suggestion : on raccroche le plus petit arbre au plus grand ; cela n’augmente pas la hauteur du
nouvel arbre sauf si les deux sont de même hauteur.
On maintient un deuxième tableau, qui, pour chaque élément donne sa hauteur.
Au moment de faire l’union, on met à jour size[u], size[v].
1 from UF import UF
2 class UF2 ( UF ):
3 def __init__ ( self , U ):
4 super ( UF2 , self ). __init__ ( U )
5 self . size = {}
6 for x in U :
7 self . size [ x ] = 0
8 def union2 ( self , u , v ):
9 chefu = self . root1 ( u )
10 chefv = self . root1 ( v )
11 if self . size [ chefu ] > self . size [ chefv ]:
12 self . Id [ chefv ] = chefu
13 else :
14 self . Id [ chefu ] = chefv
15 if self . size [ chefu ] == self . size [ chefv ]:
16 self . size [ chefv ] += 1

3.9 FIND : Compresser les chemins

Au moment de chercher le représentant d’un élément on compresse le chemin
1 from UF import UF
2 class UF3 ( UF ):
3 def __init__ ( self , U ):
4 super ( UF2 , self ). __init__ ( U )
5 self . size = {}
6 for x in U : self . size [ x ] = 0
7 def find2 ( self , u , v ):
8 return self . root2 ( u ) == self . root2 ( v )
9 def root2 ( self , u ):
10 if self . Id [ u ] != u :
11 self . Id [ u ] = self . root2 ( Id [ u ])
12 return self . Id [ u ]
13 def union2 ( self , u , v ):
14 ru = self . root2 ( u )
15 rv = self . root2 ( v )
16 if self . size [ ru ] < self . size [ rb ]:
17 self . Id [ ru ] = self . Id [ rv ]
18 else :
19 self . Id [ rv ] = self . Id [ ru ]
20 if self . size [ ru ] == self . size [ rv ]:
21 self . size [ ru ] += 1
II
Parcours d’arbres

4 Arbres binaires de recherche ABR . . . . 21

4.1 Complexité
4.2 Arbres binaires de recherche
4.3 Recherche dans un ABR
4.4 Insertion dans un ABR
 4. Arbres binaires de recherche ABR

4.1 Complexité
Pour un algorithme A on note coûtA (x) le nombre d’opérations élémentaires que l’algorithme
effectue sur une entrée x.
Complexité au pire cas : coûtA (n) = max coûtA (x), x de largeur n.
n
Coût amorti d’un algorithme A : on exécute A(x1 ) A(x2 ) ... A(xn ) ; coût amorti = 1n ∑ coûtA (xi )
i=1
Complexité en moyenne : "définition mathématique formelle de, à la louche", on a une
µ
distinction sur les entrées µ, coûtA (x) = ∑ µ(x) coûtA (x).
x∼µ

4.2 Arbres binaires de recherche

Définition 4.2.1 — Arbre binaire. Un arbre binaire est soit vide, soit une racine avec un arbre
binaire à gauche et un arbre binaire à droite.

En python :
1 class ArbreBinaire :
2 # par convention ArbreVide = None
3 def __init__ ( self , v , g = None , d = None ):
4 self . val = v
5 self . gauche = g
6 self . droite = d

Définition 4.2.2 — Arbre binaire de recherche. Un arbre binaire de recherche (ABR) est un
arbre étiqueté avec les propriétés suivantes :
1. [Link] est plus grand que toutes les valeurs de [Link].
2. [Link] est plus petit que toutes les valeurs de [Link].
 22 Chapitre 4. Arbres binaires de recherche ABR

Définition4.2.3 — Taille d’un arbre. On écrit |A| la taille de l’arbre A son nombre de sommets.
0 si l’arbre est vide
|A| =
1 + |[Link]| + |[Link]| sinon

Définition 4.2.4 — Profondeur d’un nœud. On définit la profondeur d’un nœud v dans l’arbre
A comme la longueur du chemin de la racine de A jusqu’au sous arbre de racine v :

 0 si [Link] = v
ProfA (v) = 1 + [Link] (v) si [Link] > v
1 + [Link] (v) si [Link] < v


Définition 4.2.5 — Hauteur d’un arbre. On définit la hauteur d’un arbre A :


0 si l’arbre est vide
h(A) =
1 + max(h([Link]), h([Link])) sinon

Remarque : h(A) = max ProfA (v), v ∈ A

4.3 Recherche dans un ABR

1 def TrouverABR (A , v ):
2 if v == A . val : return A
3 elif v < A . val and A . gauche is not None :
4 return TrouverABR ( A . gauche , v )
5 elif v > A . val and A . droite is not None :
6 return TrouverABR ( A . droite , v )
7 return None

ProfA (v) si v ∈ A
Proposition 4.3.1 T (A, v) =
h(A) si v ∈
/A
coûttrouverABR (A, v) ≤ T (A, v), ∀ ABR A, ∀ valeur v, |A| ≥ 1

4.3.1 Preuve par récurrence sur |A|

Hypothèse d’induction
H(n) = l’énoncé de la proposition 4.3 est vrai ∀A, v |A| ≤ n

Initialisation ("Base")
n = 1 : A a une seule valeur.
si v ∈ A alors v se trouve à la racine, 1 comparaison.
si v ∈
/ A alors on fera 5 comparaisons.

Hérédité ("Pas d’induction")

Supposons H(n) est vraie pour n ≤ 1, montrons H(n + 1).
Soit A de taille n + 1.
Si v ∈ A : Si [Link] = v on s’arrête après 1 comparaison.
Si [Link] > v : On fait 3 + T ([Link], v) comparaisons (au plus)
T ([Link], v) = 5([Link] (v) par H(|[Link]|)
On doit montrer que T ([Link], v) + 3 ≤ T (A, v)
⇔ 5([Link] (v) + 1) + 3 ≤ T (A, v) = 5(ProfA (v) + 1)
D’après la définition de ProfA (v), cas v < [Link] = 5([Link] (v) + 1 + 1)
= 5([Link] (v) + 1) + 5
Si [Link] < v : On fait T ([Link], v) + 5 comparaisons (au plus)
[...]
 4.4 Insertion dans un ABR 23

Si v ∈
/ A : Si [Link] = v, impossible
Si [Link] > v : ]comparaisons = T ([Link], v) + 3
≤ 5h([Link]) + 3 par hypothèse d’induction
≤ 5(h(A) − 1) + 3 par définition de h
≤ 5h(A)
Si [Link] < v : ]comparaisons = T ([Link], v) + 5
≤ 5h(A)

4.4 Insertion dans un ABR

4.4.1 Algorithme
1 def InsererABR (A , v ):
2 if v == A . val : raise Exception ( " v deja dans l ' arbre " )
3 if v < A . val :
4 if A . gauche is not None :
5 InsererABR ( A . gauche , v )
6 else : A . gauche = ABR (v , None , None )
7 if v > A . val :
8 if A . droite is not None :
9 InsererABR ( A . droite , v )
10 else : A . droite = ABR (v , None , None )
On souhaite faire l’analyse amortie de cet algorithme, en supposant qu’on insère les éléments
1, 2, ... N dans un ordre aléatoire.
N
coût Amorti = ∑ coûtInsérerABR (la ième valeur)
i=1
On suppose qu’il reste à insérer les valeurs x1 < x2 < ... < xN et on choisit d’insérer xi avec
une probabilité de N1 .
Si on choisit xi , on aura i − 1 éléments à gauche et n − i éléments à droite.

4.4.2 Coût moyen d’insertion de n éléments dans un ABR vide

Proposition 4.4.1 Le coût moyen d’insérer x1 < x2 < ... < xN dans un ABR initialement vide, noté
CN est : (où on compte le nombre d’appels récursifs)


 0 si N = 0
1 si N = 1

CN = N
 ∑ N1 [1 + N − 1 + Ci−1 + CN−i ] sinon


i=1
Car : coût(placer xi ) = 1
les N − 1 qui restent passent par la racine,
x1 ... xi−1 sont insérés à gauche,
xi+1 ... xN sont insérés à droite.
Proposition 4.4.2 CN = O(N log N)

Démonstration. Prenons N > 1

N
1
CN = N + N ∑ (Ci−1 +CN−i )
i=1
N N
1
= N + N ( ∑ Ci−1 + ∑ CN− j )
i=1 j=1
N−1
1
= N + N 2 ∑ Ck
k=0
24 Chapitre 4. Arbres binaires de recherche ABR
N−1
Télescopons : NCN = N 2 + 2 ∑ Ck
k=0
N−2
(N − 1)CN−1 = (N − 1)2 + 2 ∑ Ck
k=0
NCN − (N − 1)CN−1 = N 2 − (N − 1)2 + 2CN−1
NCN = 2N − 1 + (N + 1)CN−1
CN 2N−1 CN−1
N+1 = N(N+1) + N
2N−1 2
On pose : t(N) = N(N+1) ' N
CN
N+1 = t(N) + CN−1
N
CN
N+1 = t(N) + t(N − 1) + CN−1
N−2

= t(N) + t(N − 1) + t(N − 2) + CN−2

N−3

N
= ∑ t(i) + 12
i=2
N
2
≈ ∑ i + 21
i=1
N
1
≈ 2∑ i
i=1
CN
N+1 ≈ 2 ∗ N ln n
CN
On conclut que CN = 2(N + 1)N ln(N) et que le coût amorti N = 2(N + 1) ln(N)

III
Parcours de graphes

5 Parcours d’arbres k-aire . . . . . . . . . . . . . 27

5.1 Structure de donnée utilisée
5.2 Parcours en largeur des arbres
5.3 Propriétés du parcours en largeur
5.4 Parcours en profondeur des arbres
5.5 Propriétés du parcours en profondeur des arbres

6 Parcours de graphes . . . . . . . . . . . . . . . . 31
6.1 Représentation des graphes (non orientés)
6.2 Parcours en largeur des graphes
6.3 Parcours en profondeur des graphes
 5. Parcours d’arbres k-aire

On appelle arbre k-aire un arbre dont chaque nœud a au plus k fils.

Problème
Étant donné un arbre/graphe, on veut parcourir chaque sommet une et une seule fois.

5.1 Structure de donnée utilisée

Une file Q, FIFO (First In First Out), avec les opérations suivantes :
— [Link](v) : ajouter v à la fin de la file.
— u = [Link]() : retire de le premier élément de la liste et le place dans la variable u.
— [Link]() : retourne Vrai si la file est Vide, Faux sinon.
On ajoute les informations suivantes aux sommets au moment du parcours, pour chaque
sommet A :
— Datage : [Link], A. f in les instants où on découvre/quitte A
— Couleur :
— blanc : pas encore visité
— gris : en cours
— noir : terminé
— Distance : pour le parcours en largeur, la distance à la racine
1 class Noeud :
2 def __init__ ( self , val , fils =[]):
3 self . val = v
4 self . fils = fils
5 self . couleur = " blanc "

On traite les arbres à arité (nombre d’enfants) variable. Chaque sommet A peut avoir un nombre
arbitraire de fils donnés dans une liste A. f ils.
 28 Chapitre 5. Parcours d’arbres k-aire

5.2 Parcours en largeur des arbres

1 def BFS ( A ):
2 t = 0 ; d = 0
3 Q = [( A ,0)] # Queue
4 A . couleur = " gris " ;
5 A . debut = t ; t += 1
6 while not ( Q . vide ()):
7 noeud , d = Q . pop (0) # pop first
8 noeud . couleur = " noir "
9 noeud . fin = t
10 t += 1
11 for v in noeud . fils :
12 v . couleur = " gris "
13 v . debut = t ; t += 1
14 Q . append (( v , d + 1)) # push last
5.3 Propriétés du parcours en largeur
Proposition 5.3.1 Les sommets sont visités par ordre de profondeur.
On découpe en deux étapes la preuve de la proposition 5.3.1.
Proposition 5.3.2 Supposons que la file contienne les valeurs (v1 , d1 ), ... , (vk , dk ), lorsque (vi , di )
entre dans la file di = Pro fA (vi ).
Preuve de la proposition 5.3.2
Par induction sur t.
— Au temps t = 0 : La file contient (A, 0) et par définition Pro fA (t) = 0.
— Au temps t + 1 : Supposons que Q contienne (v1 , d1 ), ... , (vk , dk ) où di = Pro fA (vi ). On
retire (v1 , d1 ) de la file. On ajoute ( f1 , d1 + 1), ... , ( fe , d1 + 1) où les fi sont les fils de v1 .
Les fi sont bien à hauteur d1 + 1 dans l’arbre.
Proposition 5.3.3 Si au temps t, Q contient (v1 , d1 ), ... , (vk , dk ) alors d1 ≤ d2 ≤ ... ≤ dk et dk −
d1 ≤ 1.
Preuve de proposition 5.3.3
Par induction sur t.
— Au temps t = 0 : La file contient (A, 0), la proposition est donc vraie.
— Supposons qu’à l’instant t, Q contienne (v1 , d1 ), ... , (vk , dk ), par hypothèse d’induction, ceux-
ci vérifient la proposition. On retire (v1 , d1 ) et on ajoute ses fils ( f1 , d1 + 1), ... , ( fe , d1 + 1)
de v1 à la suite.

Vérification : 2 cas possibles d1 = dk ou d1 + 1 = dk (par hypothèse d’induction). On a

(v2 , d2 ), ... , (vk , dk ) et ( f1 , d1 + 1), ... , ( fe , d1 + 1).
1. Les distances sont encore triées, elles sont triées jusqu’à dk , puis pour f1 , ... , fe :
— dk = d1 , on ajoute d1 , ... , d1 .
— dk = d1 + 1 , on ajoute d1 + 1, ... , d1 + 1.
2. d1 + 1 − d2 < 1 ? Par hypothèse, d1 ≤ d2 ≤ d1 + 1, ok.
Proposition 5.3.4 Chaque sommet entre et sort de la file une et une seule fois.
Preuve de la proposition 5.3.4

1. Chaque sommet qui entre dans la file doit en sortir : l’algorithme ne se termine que lorsque
la file est vide.
 5.4 Parcours en profondeur des arbres 29

2. Un sommet qui est entré dans la file ne peut pas y ré-entrer. En effet, il ne rentre que quand
son père sort. Mais par récurrence son père ne peut pas ré-entrer dans la file.
3. Chaque sommet de l’arbre entre dans la file. Sinon, son père n’est pas entré, ainsi de suite
tous ses ascendants ne sont pas rentrés jusqu’à la racine.
Conclusion : Le parcours en largeur parcourt les sommets une et une seule fois par ordre
croissant de profondeur. La complexité est 2|A| (en nombre de pop() et push(v)).

5.4 Parcours en profondeur des arbres

Parcours en profondeur des arbres à arité variable :
1 def DFS (A , t = 0):
2 A . couleur = " gris " ; A . debut = t ; t += 1
3 for v in A . fils :
4 t = DFS (A , t )
5 A . couleur = " noir " ; A . fin = t ; t += 1
6 return t

Exemple

3 6

1 5 7

Remarque : si on associe au parcours en profondeur "je vais visiter i" 7→ ( et "je quitte i" 7→ )
i i
on obtient une expression correctement parenthésée ; ici : ( ( ( ( ) ) ) ( ( ) ( ) ) )
43122136557764

5.5 Propriétés du parcours en profondeur des arbres

Proposition 5.5.1 Le parcours en profondeur a les propriétés suivantes :
— ∀A [Link] < A. f in
— Avant [Link] , [Link] = "blanc"
— Entre [Link] et A. f in , [Link] = "gris"
— Après A. f in , [Link] = "noir"
Proposition 5.5.2 Pour toute paire de sommets A, A0 les intervalles IA = ([Link], A. f in) et IA0 =
(A0 .debut, A0 . f in) ne peuvent se chevaucher.
Preuve de la proposition 5.5.2
Supposons [Link] < A0 .debut < A. f in , alors entre [Link] et A. f in, les appels récursifs, y compris
à DFS(A) se sont terminés donc A0 .debut < A0 . f in < A. f in.
Proposition 5.5.3 A0 est descendant de A ⇔ [Link] < A0 .debut < A0 . f in < A. f in
30 Chapitre 5. Parcours d’arbres k-aire

Proposition 5.5.4 L’ensemble des sommets gris forment un chemin de la racine jusqu’à un sommet
de l’arbre.
Preuve de la proposition 5.5.4 Soient v1 , ... , vk les sommets gris à l’instant t. Supposons
v1 .debut < v2 .debut < ... < v1 . f in
On a montré : v1 .debut < v2 .debut < ... < v1 . f in
D’après la proposition 5.5.2, on a que vi+1 descendant de vi ∀i 1 ≤ i ≤ k. Mais il faut monter
que vi+1 est fils de vi . [...]
 6. Parcours de graphes

6.1 Représentation des graphes (non orientés)

On ajoute les informations suivantes pour chaque sommet S :
— [Link], S. f in : pour le datage, les instants où on découvre/quitte S
— [Link] :
— blanc : pas encore visité
— gris : en cours
— noir : terminé
— [Link] : pour le parcours en largeur, la distance à la racine
— [Link] : la liste des voisins.
— [Link] : le prédécesseur de S dans le parcours.
1 class Noeud :
2 def __init__ ( self , val , voisins =[]):
3 self . val = val
4 self . voisins = voisins
5 self . couleur = " blanc "
6 self . dist = 0

6.2 Parcours en largeur des graphes

Problème 1 : si on applique l’algorithme des arbres, on obtient une boucle infinie.
Problème 2 : certains sommets ne seront jamais visités.
Supposons à partir de maintenant que G est connexe.
Définition 6.2.1 — Chemins. Notations :
u →dG v : il existe un chemin de longueur d de u à v dans G.
u →∗G v : il existe un chemin de u à v dans G.
δG (u, v) : min{d : u →dG v}
Vk (s) : {v ∈ S : δG (u, v) = k}
 32 Chapitre 6. Parcours de graphes

1 def BFS ( S ):
2 t = 0 ; S . dist = 0; s . pred = None ; s . couleur = " gris "
3 Q = [ S ] # Queue
4 S . debut = t ; t += 1;
5 while not ( Q . vide ()):
6 noeud = Q . pop (0) # pop first
7 noeud . couleur = " noir "
8 noeud . fin = t ; t += 1
9 for v in noeud . voisins :
10 if v . couleur == " blanc " :
11 v . pred = noeud
12 v . dist = noeud . dist + 1
13 v . debut = t ; t += 1
14 v . couleur = " gris "
15 Q . push ( v ) # push last

Proposition 6.2.1 À l’appel de BFS(s) :

1. Les sommets (accessibles depuis s) sont parcourus par ordre de distance à s.
2. Après le parcours d’un sommet u, [Link] est égal à la distance de u à s.
3. Si le sommet u est à distance d de s, alors il existe un chemin de s à u de longueur d dont la
dernière arête est ([Link], u).
Preuve de la proposition [Link]
Il faut se convaincre qu’à l’instant où on traite le dernier sommet à distance d de s, tous les
sommets à distance d + 1 soient dans la file.
On a montré pour les arbres que la file ne contient que des sommets à distance d + 1 ; il faut
montrer que tous sont dans la file.
Posons u ∈ Vd+1 quelconque.
Comme δ (s, u) = d + 1 , ∃v , δ (s, u) = d et (u, v) ∈ A.
Par induction, v a été traité avec les sommets de distance d et donc u :
— s’il n’avait pas déjà été visité au moment de traiter v, a été ajouté à la file
— s’il avait déjà été visité, u a déjà été mis dans la file. Il a dû être mis dans la file pour un autre
sommet v0 .
δ (s, v0 ) est nécessairement égal à d sinon δ (s, u) = δ (s, v0 ) + 1 < d + 1.

Proposition 6.2.2 Tous les sommets accessibles à partir de s sont visités une et une seule fois.

Définition 6.2.2 — Graphe des prédécesseurs. Après le parcours (BFS ou DFS) à partir
de s ∈ S d’un graphe G = (S, A) , on appelle graphe des prédécesseurs : G pred = (S, A0 ) avec
A0 = {(u, [Link]), u ∈ S \ {S}}

Proposition 6.2.3 Si G est connexe, G pred est un arbre ; on l’appelle arbre de parcours.
Preuve de la proposition 6.2.3
G pred a n = |S| sommets et n − 1 arêtes ; G pred est connexe car on a parcouru tous les sommets
en passant par des arêtes du graphe.
Proposition 6.2.4 La complexité de BFS(S) en nombre de comparaisons est : ∑ ∑ 1 = 2|A| (car
x∈S v∈x
∑ représente la boucle while, 1 fois pour chaque sommet retiré de la file ; ∑ la boucle for)
x∈S v∈x
 6.3 Parcours en profondeur des graphes 33

6.3 Parcours en profondeur des graphes

6.3.1 Version récursive
1 def DFS (S , t = 0):
2 S . couleur = " gris " ; S . debut = t ; t += 1
3 for v in A . fils :
4 if v . couleur == " blanc " :
5 v . pred = S
6 t = DFS (v , t )
7 S . couleur = " noir " ; S . fin = t ; t += 1
8 return t
6.3.2 Version itérative
1 def DFS ( S ):
2 pile = [ S ]; S . couleur = " gris "
3 while not len ( pile ) == 0:
4 next = pile [ -1] # head
5 for v in next . voisins :
6 if v . couleur == " blanc " :
7 v . couleur = " gris "
8 pile . push ( v )
9 break
10 else :
11 next . couleur = " noir " ; pile . pop ( -1)
Exemple

2 4 5

3 6 7

F IGURE 6.1 – G

Remarque : si on associe au parcours en profondeur "je vais visiter i" 7→ ( et "je quitte i" 7→ )
i i
on obtient une expression correctement parenthésée ; ici : ( ( ( ( ( ( ) ) ( ) ) ( ) )
12346776554321

Définition 6.3.1 — Chemins. On écrit :

— u →∗G v : il existe un chemin de u à v dans G.
— u ⇒∗G v : il existe un chemin orienté de u à v dans G pred = {([Link], s), s ∈ S}.

Théorème 6.3.1 — Chemin blanc. Si u ⇒∗G pred v ⇔ au temps t = [Link] , un chemin blanc
relie u à v dans G.
34 Chapitre 6. Parcours de graphes

2 4 5

3 6 7

F IGURE 6.2 – G pred

Proposition 6.3.2 Le parcours en profondeur a les propriétés suivantes : ∀ sommet u ∈ S

1. [Link] < u. f in
2. ∀t < [Link] [Link] = blanc
3. ∀t : [Link] ≤ t ≤ u. f in [Link] = gris
4. ∀t > u. f in [Link] = noir
Proposition 6.3.3 Pour toute paire de sommets u, v les intervalles Iu = ([Link], u. f in) et Iv =
([Link], v. f in) ne peuvent se chevaucher.
Proposition 6.3.4 Pour toute paire de sommets (u v) u ⇒∗G v ⇔ [Link] < [Link] < v. f in < u. f in
Preuve du théorème du "chemin blanc"
(⇒) Supposons que u ⇒∗G pred v par le chemin u = u0 ⇒1G pred u1 ⇒1G pred ... ⇒1G pred uk = v .
D’après la proposition 6.3.4 les intervalles s’emboîtent : ( ( ( ... ( ) ... ) ) )
u0 u1 u2 uk uk u2 u1 u0
D’après la proposition 6.3.2 : au temps t = [Link] u1 , u2 , ... uk sont blancs.
Donc le chemin u = u0 ⇒1G pred u1 ⇒1G pred ... ⇒1G pred uk = v est blanc.
(⇐) Supposons qu’il existe un chemin blanc de u à v dans G au temps t = [Link]
u = u0 ⇒1G pred u1 ⇒1G pred ... ⇒1G pred uk ⇒ ... ⇒ ui−1 → ui → ... uk = v
Soit i le point le plus petit tel que (ui−1 , ui ) ∈
/ G pred .
On va montrer qu’on peut trouver un chemin dans G pred .
Posons k < i le plus petit tel que (uk , ui ) ∈ G .
Examinons la structure au moment t 0 = uk . f in .
On veut montrer qu’on peut aller jusqu’à i avec un chemin dans G pred .
Au temps t 0 , quelle est la couleur de ui ?
• ui = blanc ? Non, on visite tous les voisins blancs de uk avant uk . f in
• ui = gris ? On avait u0 ⇒∗ ui ⇒ uk or k < i , donc impossible
• ui = noir ? 2 possibilités :
◦ Soit ( ( ) ( ) ) d’après la proposition 6.3.3
u0 ui ui uk uk u0
◦ Soit ( ( ( ) ) ) d’après la proposition 6.3.4.
u0 uk ui ui uk u0
Dans les deux cas u0 ⇒∗G pred ui

Applications des parcours de graphes

— Recherche de cycles (deadlock, BDD)
— Plus courts chemins dans les graphes
— Détection de composante connexe (reconnaissance de motifs dans une image)
— Tri topologique (gestion de projet)
— Recherche de stratégie optimale dans les jeux.
IV
Algorithmes de graphes

7 Algorithme de Kruskal . . . . . . . . . . . . . . . 37
7.1 Implémentation de l’algorithme de Krukal
7.2 Correction de l’algorithme de Kruskal

8 Algorithme de Prim . . . . . . . . . . . . . . . . . . 39
8.1 Implémentation de l’algorithme de Prim (version
optimisée)
8.2 Complexité de l’algorithme de Prim

9 Les plus cours chemins : Dijkstra . . . . . . 41

9.1 Algorithme de Dijkstra
9.2 Preuve de l’algorithme de Dijkstra

10 Algorithme de Bellman-Ford . . . . . . . . . 45
10.1 Idée
10.2 Implémentation en Python
10.3 Preuve

11 All pairs shortest paths . . . . . . . . . . . . . . . 47

11.1 Dijkstra, plusieurs fois
11.2 Modification de Bellman-Ford
11.3 En doublant la longueur des chemins à chaque
itération
11.4 Algorithme de Floyd-Warshall

12 Cycles négatifs . . . . . . . . . . . . . . . . . . . . . . 51
12.1 Algorithme pour détecter les cycles négatifs

Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
 7. Algorithme de Kruskal

Définition 7.0.2 — Graphe valué. Un graphe G = (S, A) est valué (ou pondéré) si on y associe
une fonction de coût sur ses arêtes : w : A −→ R+ .

Définition 7.0.3 — Arbre couvrant minimal. Soit G = (S, A) et w une fonction de coût, trou-
ver A0 ⊆ A tel que T = (S, A0 ) soit un arbre couvrant de cout minimal coût(T ) = ∑ w(u, v)
(u, v)∈A0

7.1 Implémentation de l’algorithme de Krukal

1 from UF import UF
2 def Kruskal (G , w ):
3 T = []; cout = 0;
4 A = G . A # l ' ensemble des arretes de G
5 S = sorted ( A ) # A trie selon w croissant
6 for (u , v ) in S :
7 if not UF . find (u , v ): # si (u , v ) ne forme pas de cycle
8 T . append (( u , v ))
9 cout += w [( u , v )]
10 UF . union (u , v )
11 return (T , cout )

Complexité : m log m avec m = nombre d’arêtes

7.2 Correction de l’algorithme de Kruskal
Définition 7.2.1 — Arbres couvrants minimaux. ACM(G, w) = l’ensemble des arbres cou-
vrants minimaux de G = (S, A) : T 0 = (S, A0 ) avec A0 ⊆ A.

Définition 7.2.2 — Compatibilité. Pour toute solution partielle T 0 ⊆ G , on dit que T 0 est
compatible avec ACM(G, w) et on note T 0 v ACM(G, w) si ∃T ∈ ACM(G, w) tel que T 0 ⊆ T .
 38 Chapitre 7. Algorithme de Kruskal

7.2.1 Lemme d’optimalité

Soit G connexe, G = (S, A) et w : A −→ R+ . Si T 0 v ACM(G, w) , T 0 = (S, A0 ) et S = S1 ∪ S2
S1 ∩ S2 = ∅ tels que A0 ∩ (S1 × S2 ) = ∅, alors on peut ajouter (u, v) ∈ S1 × S2 , de coût minimal
parmi les arêtes S1 × S2 ∩ A. Autrement dit, T ∪ {(u, v)} v ACM(G, w)

Preuve
On a G = (S, A) connexe, w ←− R+ S = S1 ∪ S2 S1 ∩ S2 = ∅
T 0 ⊆ T ∈ ACM(G, w)
T 0 ∩ S1 × S2 = ∅
Soit (u, v) de moindre coût parmi A ∩ S1 × S2
On veut montrer que T 0 ∪ (u, v) v ACM(G, w)
— cas 1 : si (u, v) ∈ T alors T 0 ∪ (u, v) ⊆ ACM(G, w)
— cas 2 : si (u, v) ∈/ T , comme G est connexe, T est un ACM.
T est connexe, (u0 , v0 ) ∈ S1 × S2 ∩ T car il existe un chemin de u à v dans T .
On a pris (u, v) de poids minimal ; donc w(u, v) ≤ (u0 , v0 ) .
∼
Regardons T = T \ {(u0 , v0 )} ∪ {(u, v)}
1. coût de T : coût dans S1 + coût dans S2 + w(u0 , v0 )
∼
coût de T : coût dans S1 + coût dans S2 + w((u, v)) or (u, v) ≤ w(u0 , v0 )
∼
Donc coût de T < coût de T∼
2. Si T est un arbre couvrant, T l’est aussi.
∼
Donc T ∈ ACM(G, w) et T 0 ∪ (u, v) ⊆ ACM(G, w)
Dans le cas de l’algorithme de Kruskal, supposons qu’à une itération donnée, on ait choisi les
arêtes T 0 et on a montré T v ACM(G, w) .
Posons S1 la composante connexe qui contient u et S2 = S \ S1 .
(u, v) que choisit Kruskal est celle de poids minimal parmi les arêtes qui restent qui ne forme pas
de cycle, comme u ∈ S1 , forcément v ∈ / S1 . Donc on peut l’ajouter d’après le lemme d’optimalité.
 8. Algorithme de Prim

On fait pousser un arbre T .

À chaque instant T est un arbre.
On ajoute l’arête de coût minimal parmi les arêtes qui sortent de l’arbre.
Pour trouver la meilleure on utilise une file de propriété (un tas min).

8.1 Implémentation de l’algorithme de Prim (version optimisée)

On met les sommets dans le tas et on note le prédécesseur du sommet (arête) qui donne la
meilleure priorité. En cours d’algorithme la priorité des sommets dans le tas peut changer.
1 from FilePriorite import FilePriorite
2 def Prim (G , w , s ):
3 inf = float ( " inf " )
4 H = FilePriorite ()
5 T = []
6 s . priorite = 0; H . inserer (0 , s )
7 for u in G . sommets :
8 u . pred = None
9 if u != s :
10 H . inserer ( inf , u )
11 u . priorite = inf
12 while not H . is_empty ():
13 p , u = H . pop_min ()
14 if u . priorite != inf :
15 if u . pred is not None : T . append (( u . pred , u ))
16 for v in u . voisins :
17 if v . idx is not None : # v n ' est pas sorti du tas
18 if w [( u , v )] < v . priorite :
19 v . priorite = w [( u , v )]
20 H . diminuer_cle ( v . idx , v . priorite )
21 v . pred = u
22 return T
 40 Chapitre 8. Algorithme de Prim

Exemple

A 1 B
Tas : (A, 0) (B, ∞) (C, ∞) (D, ∞) (E, ∞)
7 3 (A, 0) (B, ∞) (C, ∞) (D, ∞) (E, ∞)
(B, 1) (C, 7) (D, 18) (E, ∞)
18 C
(C, 3) (D, 18) (E, ∞)
2 (D, 3) (E, ∞)
(E, 10)
D 10 E

8.2 Complexité de l’algorithme de Prim

Initialisation : n× insérer = O(n log n)
Boucle while : n fois
Corps de la boucle : pop + f or × update = log n + deg(u) × log n ≈ n log n + 2m log n
 9. Les plus cours chemins : Dijkstra

Communisme vs Capitalisme

A A
5 5 5 5
B 3 C B 3 C

F IGURE 9.1 – Arbre Couvrant minimal, coût = 8 F IGURE 9.2 – Plus courts chemins depuis A

Étant donné un graphe valué G, w et un sommet de départ s. On veut calculer les plus courts
chemins de s à v dans G ∀v ∈ S.
Définition 9.0.1 — Notations. Si C = (s = u0 , u1 , u2 , ... uk = v) est un chemin de s à v dans G,
on écrit :
C
— s −→G v
k
— w(C) = ∑ w(ui−1 , ui )
i=1
C
— δ (s, v) = min{w(C) : s −→G v}
C
Proposition 9.0.1 On peut toujours trouver des chemins Cu s −→ u tel que l’union des Cu forme
un arbre.
Preuve Supposons qu’on ait 2 sommets u, v des plus courts chemins Cu , Cv dont l’union forme
un cycle.
C1 C2
Les segments C1 , C2 x −→ y x −→ y ont le même coût, sinon supposons w(C1 ) < w(C2 ) alors
il y a un chemin plus court de s à v qui passe par C1 ; C2 n’est pas un plus court chemin, impossible.

9.1 Algorithme de Dijkstra

On modifie l’algorithme de Prim, la notion de priorité change, maintenant c’est la distance à s.
 42 Chapitre 9. Les plus cours chemins : Dijkstra

améliorer la priorité ≡ améliorer la distance à s

1 from FilePriorite import FilePriorite
2 def Dijkstra (G , w , s ):
3 inf = float ( " inf " )
4 H = FilePriorite ()
5 T = []
6 s . priorite = 0; H . inserer (0 , s )
7 for u in G . sommets :
8 u . pred = None
9 if u != s :
10 H . inserer ( inf , u )
11 u . priorite = inf
12 while not H . is_empty ():
13 p , u = H . pop_min ()
14 if u . priorite != inf :
15 if u . pred is not None : T . append (( u . pred , u ))
16 for v in u . voisins :
17 if v . idx is not None : # v n ' est pas sorti du tas
18 if u . priorite + w [( u , v )] < v . priorite :
19 v . priorite = u . priorite + w [( u , v )]
20 H . diminuer_cle ( v . idx , v . priorite )
21 v . pred = u
22 return T

9.2 Preuve de l’algorithme de Dijkstra

Définition 9.2.1 Notons [Link] la valeur de [Link] à la t ième itération.

/ tas alors [Link] = δ (s, u).

Théorème 9.2.1 À l’itération t, si u ∈

On utilise sans démontrer trois propriétés :

(P1) S’il n’y a pas de chemin de s à u alors [Link] = ∞ ∀t
(P2) "Borne supérieure" : ∀u, ∀ [Link] ≥ δ (s, u) et [Link] ≥ [Link]+1
(P3) Si s −→∗G u −→1 v est un plus court chemin de s à v et [Link] = δ (s, u),
0
alors ∀t 0 > t [Link] = δ (s, v)
Preuve du théorème
Supposons qu’à l’itération t, u sorte du tas.
Regardons T t l’ensemble des arêtes déjà choisies.
/ Tt.
Soit C un plus court chemin de s à u, et x, y la première arête de C telle que (x, y) ∈
C ⊆T
1 / 1
∈T C 2
s −→ x −→ y −→ u
On va montrer que y = u.
(I) Montrons que : [Link] = δ (s, y)
(*) On utilise le fait que sur un plus court chemin de u0 à uk les segments initiaux de u0 à ui
(avec 0 ≤ i ≤ k) sont aussi des plus courts chemins
On a que x ∈ T t , supposons qu’il a été ajouté à l’instant t 0 < t.
0
Par hypothèse d’induction : [Link] = δ (s, x)
0
À l’itération t 0 , y est encore dans le tas et y est voisin de x, et on aura posé [Link] ≤
0
[Link] + w(x, y) or s −→i x −→1 y est un plus court chemin (par (*)).
0
[Link] ≤ δ (s, x) + w(x, y) = longueur du chemin = δ (s, y) et par P2 [Link] = δ (s, y)
(II) On montre que C2 = ∅
Donc on conclut que y = u, et par (I) [Link] = [Link] = δ (s, y) = δ (s, u)
9.2 Preuve de l’algorithme de Dijkstra 43

À l’itération t, y ∈ T t , mais y a une priorité 6= ∞ donc y est dans le tas, tout comme u qui a
été choisi.
[Link] ≤ [Link] car u sort du tas
= δ (s, y) (II)
≤ δ (s, u) car y précède u sur un plus court chemin
≤ [Link] (P2)
⇒ toutes ces quantités sont égales ⇒ y = u
 10. Algorithme de Bellman-Ford

Cet algorithme permet de trouver les plus courts chemins depuis un sommet source donné. Il est
cependant moins performant que Dijkstra, mais est distribuable, chaque sommet du réseau connaît
ses voisins, propage les résultats des calculs intermédiaires à ses voisins.

10.1 Idée
Commencer avec d(s) = 0 et d(u) = ∞ ∀u 6= s.
À chaque itération, on parcourt toutes les arêtes du graphe ; (u, v) ∈ A : si d(u) + w(u, v) < d(v)
On pose d(v) = d(u) + w(u, v) et pred(v) = u.

Exemple

B 4 D
2 1 2
A 8 E
12 1 4
C

2 2 2
B B D 6 B D 5

A A E A E
3 3
t =1 C t =2 C t =3 C
12 10 4
 46 Chapitre 10. Algorithme de Bellman-Ford

On remarque qu’à l’itération t on trouve des plus courts chemins qui parcourent au plus t arêtes.
Un plus court chemin de s à u parcourt au plus n − 1 arêtes. Pour que l’algorithme soit correct,
il suffit de montrer qu’à l’itération t on a calculé les plus courts chemins passant par au plus t arêtes
et répéter n − 1 fois pour avoir tous les plus courts chemins de s aux autres sommets.

10.2 Implémentation en Python

1 def Bellman_Ford (G , w , s ):
2 inf = float ( " inf " )
3 for u in G . sommets :
4 if u != s : u . dist = inf
5 u . pred = None
6 s . dist = 0
7 for t in range (1 , len ( G . sommets )):
8 for u in G . sommets :
9 for v in u . voisins :
10 if v . dist > u . dist + w [( u , v )]:
11 v . dist = u . dist + w [( u , v )]
12 v . pred = u
13 return [( u . pred , u ) for u in G . sommets if u != s ]
Complexité : n × m
10.3 Preuve
Définition 10.3.1 On note :
— δ t (u, v) = longueur du plus court cheminde u à v en passant par au plus t arêtes.
— [Link] t = valeur de [Link] à l’itération t.
Proposition 10.3.1 ∀v ∈ S d t (v) = δ t (s, v)

Démonstration. Par récurrence sur t.

Lorsque t = 0, un seul chemin de longueur 0 de s à s.
À l’itération t > 0, par hypothèse d’induction, ∀x [Link] t−1 = δ t−1 (s, x)
Soit Cv un plus court chemin de s à v parcourant au plus t arêtes. Si Cv a moins de t arêtes
0
alors on l’a découvert à une itération précédente t 0 < t donc [Link] t = δ t−1 (s, v). Si Cv a t arêtes, le
chemin s −→ x est un plus court chemin qui parcourt au plus t − 1 arêtes (sinon on trouverait un
meilleur chemin de t arêtes vers v).
On peut appliquer l’hypothèse d’induction x [Link] t−1 = δ t−1 (s, x) .
À l’itération t on considère x et son voisin v et on posera :
[Link] ≤ [Link] + w(x, v)
= δ t−1 (s, x) + w(x, v) 
= δ t (s, v)
 11. All pairs shortest paths

"Plus courts chemins toutes sources toutes destinations"

Étant donné un graphe G et une fonction de coût w, on veut trouver ∀u, v ∈ S un plus court
chemin de u à v.

11.1 Dijkstra, plusieurs fois

Lancer Dijkstra sur tous les sommets ; complexité en temps : n × (m + n log n) (n sommets, m
arêtes).

11.2 Modification de Bellman-Ford

Idée : Au temps t, calculer δ t (u v) en utilisant δ t−1 (u v) ∀u, v.
Initialement δ 1 (u v) = w(u, v) ∀u, v
∀t, calculer δ t+1 en fonction de δ t ?
On a pour u, v, un plus court chemin de longueur au plus t.
Pour obtenir un plus court chemin de u à v en passant par au plus t + 1 arêtes, il suffit de prendre
min{δ t (u v), min{δ t (u x) + w(x, v)}} x voisins de v.
On peut s’arrêter lorsque t = n − 1 (après on forme des cycles).
On note Pred[u][v] le prédécesseur de v dans le plus court chemin de u à v.

B 2 C
20 2
A 40 D
2 2
F 2 E
 48 Chapitre 11. All pairs shortest paths

D Pred
A B C D E F A B C D E F
A 0 20 - - - 2 A A A - - - A
B 20 0 2 - - - B A B B - - -
t =1 C - 2 0 2 - 40 C - B C C - C
D - - 2 0 2 - D - - C D D -
E - - - 2 0 2 E - - - D E E
F 2 - 40 - 2 0 F A - C - E F

A B C D E F A B C D E F
A 0 20 22 - - 2 A A A B - - A
B 20 0 2 4 - 22 B A B B C - A
t =2 C 22 2 0 2 4 40 C B B C C D C
D - 4 2 0 2 4 D - C C D D E
E - - 4 2 0 2 E - - D D E E
F 2 22 40 4 2 0 F A A C E E F
etc.

Pour trouver le plus court chemin de C à F il faut attendre t = 3, de AB, t = 5 = n − 1 .

Implémentation
Dans l’implémentation de l’algorithme il va falloir faire des copies, sinon à l’instant t, D contient
un mélange de δ t et δ t+1 .
1 from utils import dcopy
2 def PCC1 (G , w ):
3 inf = float ( " inf " )
4 D = { u :{ u : inf for u in G . sommets } for u in G . sommets }
5 Pred = { u :{ u : None for u in G . sommets } for u in G . sommets }
6 for u in G . sommets :
7 for v in G . sommets :
8 D [ u ][ v ] = w [ u ][ v ]
9 Pred [ u ][ v ] = None if w [ u ][ v ] == inf else u
10 D_next = dcopy ( D )
11 Pred_next = dcopy ( Pred )
12 for t in range (2 , len ( G . sommets )):
13 for u in G . sommets :
14 for v in G . sommets :
15 for x in v . voisins :
16 if D_next [ u ][ v ] > D [ u ][ x ] + w [ x ][ v ]:
17 D_next [ u ][ v ] = D [ u ][ x ] + w [ x ][ v ]
18 Pred_next [ u ][ v ] = x
19 D = dcopy ( D_next )
20 Pred = dcopy ( Pred_next )
21 return (D , Pred )

11.3 En doublant la longueur des chemins à chaque itération

t t−1
Idée : Au temps t, calculer δ 2 (u, v) ∀u, v en utilisant δ 2 (u, v) ∀u, v .
t
Initialement : δ 2 (u, v) = w(u, v) ∀u, v
t+1 t+1
∀t , calculer δ 2 en fonction de δ 2 ?
 11.4 Algorithme de Floyd-Warshall 49

∀u , un plus court chemin de longueur au plus 2t+1 = 2 × 2t arêtes est composé de 2 plus courts
chemins de longueur au plus 2t .
≤ 2t ≤ 2t
u −−−−−−−−−→ x −−−−−−−−−→ v

Pour obtenir un plus court chemin de u à v en passant par au plus 2t+1 arêtes il suffit de prendre :
t t t
min{δ 2 (u, x), min{δ 2 (u, x) + δ 2 (x, v)}}
x∈S

t
On peut s’arrêter lorsque δ 2 ≥ n − 1 .

Implémentation
On note Pred[u][v] le prédécesseur de v dans le plus court chemin de u à v.
1 from utils import dcopy
2 from math import log , ceil
3 def PCC1 (G , w ):
4 inf = float ( " inf " )
5 D = { u :{ u : inf for u in G . sommets } for u in G . sommets }
6 Pred = { u :{ u : None for u in G . sommets } for u in G . sommets }
7 for u in G . sommets :
8 for v in G . sommets :
9 D [ u ][ v ] = w [ u ][ v ]
10 Pred [ u ][ v ] = None if w [ u ][ v ] == inf else u
11 D_next = dcopy ( D )
12 Pred_next = dcopy ( Pred )
13 for t in range (2 , ceil ( log ( len ( G . sommets ) - 1 , 2))):
14 for u in G . sommets :
15 for v in G . sommets :
16 for x in G . sommets :
17 if D_next [ u ][ v ] > D [ u ][ x ] + w [ x ][ v ]:
18 D_next [ u ][ v ] = D [ u ][ x ] + w [ x ][ v ]
19 Pred_next [ u ][ v ] = Pred [ x ][ v ]
20 D = dcopy ( D_next )
21 Pred = dcopy ( Pred_next )
22 return (D , Pred )

11.4 Algorithme de Floyd-Warshall

Idée : Supposons que les sommets soient numérotés de 1 à n.
À chaque itération t, on va calculer la longueur des plus courts chemins de u à v ∀u, v ∈ S qui
passent uniquement par les sommets {1, ..., t}
Appelons δ R (u, x) la longueur du plus court chemin de u à v passant uniquement par des
R⊆S
sommets appartenant à R.
De façon générale, si on a calculé ∀u, v δ 1, ... , k (u, v)

δ 1, ... , k (u, v) = min{δ 1, ..., k (u, v), δ 1, ... , k (u, k + 1)δ 1, ... , k (k + 1, v)}
 50 Chapitre 11. All pairs shortest paths

A B C D E F A B C D E F
A 0 20 - - - 2 A - - - - - -
B 20 0 2 - - - B - - - - - -
C - 2 0 2 - 40 C - - - - - -
D 40 - 2 0 2 - D - - - - - -
E - - - 2 0 2 E - - - - - -
F 2 - - - 2 0 F - - - - - -

t =1 : δ (B, F) = 22 t =3 : δ (A, D) = δ (A, C) + δ (C, D) = 22 + 2 = 24

t =2 : δ (A, C) = 22 δ (D, F) = δ (D, C) + δ (C, F) = 2 + 24 = 26
δ (C, F) = 26 δ (B, D) = δ (B, C) + δ (C, D) = 2 + 2 = 4

Implémentation
1 from utils import dcopy
2 def Floyd_Warshall (G , w ):
3 inf = float ( " inf " )
4 D = { u :{ u : inf for u in G . sommets } for u in G . sommets }
5 Pred = { u :{ u : None for u in G . sommets } for u in G . sommets }
6 for u in G . sommets :
7 for v in G . sommets :
8 D [ u ][ v ] = w [ u ][ v ]
9 Pred [ u ][ v ] = None if w [ u ][ v ] == inf else u
10 D_next = dcopy ( D )
11 Pred_next = dcopy ( Pred )
12 for x in G . sommets :
13 for u in G . sommets :
14 for v in G . sommets :
15 if D [ u ][ x ] + D [ x ][ v ] < D_next [ u ][ v ]:
16 D_next [ u ][ v ] = D [ u ][ x ] + D [ x ][ v ]
17 Pred_next [ u ][ v ] = Pred [ x ][ v ]
18 D = dcopy ( D_next )
19 Pred = dcopy ( Pred_next )
20 return (D , Pred )
 12. Cycles négatifs

k−1
Définition 12.0.1 — Cycle négatif. Un cycle C = {u1 , ... , uk est négatif si ∑ w(ui , ui + 1) +
i=1
w(uk , u1 < 0. Pour simplifier les équations, on écrit WC = ∑ w(u, v)
(u, v)∈C

Remarque : l’algorithme de Dijkstra ne marche pas pour les graphes avec des poids négatifs.

12.1 Algorithme pour détecter les cycles négatifs

Supposons qu’on vient d’exécuter Bellman-Ford et qu’on a dist[s][v] ∀v. On exécute alors
un tour de boucle supplémentaire, si on découvre un meilleur chemin (ce qui n’est normalement
pas possible, car on a trouvé tous les plus courts chemins), c’est qu’il y a un cycle négatif.
1 def CycleNegatif (G , w ):
2 s = G . sommets [0] # un sommet de depart
3 Pred = Bellman_Ford (G , w , s )
4 for u in G . sommets :
5 for v in u . voisins :
6 if v . dist > u . dist + w [( u , v )]:
7 return True
8 return False
Complexité : Bellman-Ford + O(n + m)
 Index

Composante connexe . . . . . . . . . . . . . . . . . . . . 13
Connexe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
A Cycle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
Cycle négatif . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
ACM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
Algorithme de Kruskal . . . . . . . . . . . . . . . . . . . 37
Algorithme de Prim . . . . . . . . . . . . . . . . . . . . . 39
Arbre . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 D
Arbre binaire . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
Dijkstra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
Arbre binaire de recherche . . . . . . . . . . . . . . . 21
Arbre couvrant . . . . . . . . . . . . . . . . . . . . . . 10, 11
Arbre couvrant minimal . . . . . . . . . . . . . . . . . . 37
Arbre de parcours . . . . . . . . . . . . . . . . . . . . . . . 32 F

FIND . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
B Floyd-Warshall (Algorithme) . . . . . . . . . . . . . 49

Bellman-Ford (algorithme) . . . . . . . . . . . . . . . 45

G
C Graphe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
Graphe des prédécesseurs . . . . . . . . . . . . . . . . 32
Chemin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
Graphe pondéré . . . . . . . . . . . . . . . . . . . . . 11, 37
Chemin simple . . . . . . . . . . . . . . . . . . . . . . . . . 10
Chemins . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31, 33 Graphe valué . . . . . . . . . . . . . . . . . . . . . . . . 11, 37
Coût amorti . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
Compatibilité . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
Complexité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 H
Complexité au pire cas . . . . . . . . . . . . . . . . . . . 21
Complexité en moyenne . . . . . . . . . . . . . . . . . 21 Hauteur (Arbre) . . . . . . . . . . . . . . . . . . . . . . . . . 22
54 INDEX

Insertion (ABR) . . . . . . . . . . . . . . . . . . . . . . . . 23

Kruskal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

Liste d’adjacence . . . . . . . . . . . . . . . . . . . . . . . 10

Matrice d’adjacence . . . . . . . . . . . . . . . . . . . . . 10

Parcours en largeur . . . . . . . . . . . . . . . . . . 28, 31

Parcours en profondeur . . . . . . . . . . . . . . . . . . 33
Prim . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
Problème . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
Profondeur d’un nœud (Arbre) . . . . . . . . . . . 22

Recherche dans un ABR . . . . . . . . . . . . . . . . . 22

Structure de données . . . . . . . . . . . . . . . . . . . . 11

UNION . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15