Etude des problèmes de maximisation dans un réseau de ot

Vous n'aurez pas mon nom :)

Juin 2023

Résumé : On se propose d'étudier deux algorithmes permettant de résoudre le problème de maximisation du ot,
le second étant implémenté à l'aide d'une structure d'arbres dynamiques conférant une complexité O(nm log2 (n))
pour le calcul d'un ot maximal avec n et m respectivement le nombre de sommets et d'arcs du réseau.

1 Introduction

1.1 Contexte
Historiquement, la formalisation des problèmes de ot maximal fut introduite dans les années 1950, par Ford
et Fulkerson pour répondre à la problématique suivante [1] :  On se donne un réseau ferré reliant 2 villes au
moyen de plusieurs villes intermédiaires, où à chaque lien est assigné un nombre représentant sa capacité. En
supposant un état normal de marche, trouver un ot maximal d'une ville donnée à l'autre. . Ils proposent alors
une première méthode de résolution du problème de maximisation du ot. Plusieurs années plus tard, sans avoir
entendu parler de cette méthode, le chercheur soviétique Yem Dinitz publie une méthode similaire de résolution,
qui propose une complexité asymptotique plus faible que celle de la méthode de Ford-Fulkerson dans le cas de
réseaux connexes. Le problème de maximisation du ot peut être utilisé pour diverses applications, de la prévision
de la congestion du trac d'un réseau de transport à l'optimisation du transport d'électricité dans une ville.

1.2 Cadre de l'étude

On considère un graphe orienté G = (V, E), accompagné d'une application de capacité c : V 2 → R+ . On convient
que ∀(u, v) ∈ V 2 \E, c(u, v) = 0. On distingue deux sommets (s, t) ∈ V 2 , respectivement la source et le puits.
Les lettres s et t désigneront systématiquement la source et le puits par la suite. Quitte à restreindre le réseau
envisagé, on suppose que pour tout v ∈ V , il existe un chemin de s à t passant par v dans G. Le quadruplet
(G, c, s, t) est appelé réseau de ot.

5
v2 v4

6 3 11 6

s v3 4 2 t

7 9 5 5

v1 v5
4

Figure 1  Un réseau de ot

Dénition : Un ot dans un réseau (G = (V, E), c, s, t) est une application f : V 2 → R satisfaisant les 3
propriétés suivantes :
(i ) Contrainte de capacité : ∀(u, v) ∈ V 2 , f (u, v) ≤ c(u, v)
(ii ) Antisymétrie : ∀(u, v) ∈ V 2 , f (u, v) = −f (v, u)
(iii ) Conservation du ot : ∀u ∈ V \{s, t},
P
f (u, v) = 0
v∈V
On dénit la valeur du ot : |f | = f (s, v).
P
v∈V
Le problème de maximisation du ot est alors, étant donné un réseau, de trouver un ot de valeur maximale
parmi les valeurs des ots du réseau.

1
2 Algorithme de Ford-Fulkerson

Dénition : Soit (G = (V, E), c, s, t) un réseau de ot et f un ot dans G. On appelle capacité résiduelle du
réseau pour f l'application cf : (u, v) ∈ V 2 7→ c(u, v) − f (u, v). On dénit alors le graphe résiduel Gf = (V, Ef )
où Ef = {(u, v) ∈ E | cf (u, v) > 0}.

Algorithme 1 Algorithme de Ford-Fulkerson

Entrée: Un réseau (G = (V, E), c, s, t)
Sortie: Un ot f du réseau vériant |f | maximale
1: pour tout (u, v) ∈ V 2 faire
2: f (u, v) ← 0
3: n pour
4: tant que il existe un chemin p de s à t dans Gf faire
5: cf (p) ← min{cf (u, v) | (u, v) ∈ p}
6: pour tout (u, v) ∈ p faire
7: f (u, v) ← f (u, v) + cf (p)
8: f (v, u) ← −f (u, v)
9: n pour
10: n tant que
11: Renvoyer f

L'algorithme de Ford-Fulkerson est un algorithme glouton qui trouve des chemins de s à t dans le graphe résiduel
(dits chemins augmentants). Si un tel chemin existe, c'est que tout arc (u, v) du chemin n'est pas encore saturé,
c'est-à-dire f (u, v) < c(u, v). On peut donc augmenter le ot sur ce chemin, à condition de le baisser sur le chemin
inverse (pour garantir l'antisymétrie).
DénitionP: On P appelle coupe du graphe G toute partition (S, T ) de V telle que s ∈ S et t ∈ T . On note alors
c(S, T ) = c(v, w).
v∈S w∈T
Lemme : Montrons que pour tout ot f dans G et pour toute coupe (S, T ) de G, |f | ≤ c(S, T ).

On a |f | =
X
f (s, v)
v∈V

f (u, v) par conservation du ot

X X X
= f (s, v) +
v∈V u∈S\{s} v∈V
XX
= f (u, v)
u∈S v∈V
XX XX
= f (u, v) + f (u, v)
u∈S v∈S u∈S v∈T

Or f (u, v) par antisymétrie

XX XX XX XX
f (u, v) = f (v, u) = − f (u, v) = −
u∈S v∈S v∈S u∈S v∈S u∈S u∈S v∈S

Donc |f | = f (u, v) (*)

XX

u∈S v∈T

c(u, v) = c(S, T ) par contrainte de capacité

XX
≤
u∈S v∈T

Théorème (Max ow-min cut ) : Soit (G = (V, E), c, s, t) un réseau et f un ot. Les propriétés suivantes sont
équivalentes :
(i) f est un ot maximal dans G.
(ii) Il n'existe pas de chemin de s à t dans Gf .
(iii) Il existe une coupe (S, T ) de G telle que |f | = c(S, T ).
Démonstration. (i) =⇒ (ii) : Supposons qu'il existe un chemin de s à t dans Gf . Alors il existe un ot bloquant
f ′ dans GL avec |f ′ | > 0 , et f + f ′ est un ot dans G de valeur |f + f ′ | = |f | + |f ′ | > |f | ce qui contredit la
maximalité de f .

(ii) =⇒ (iii) : Soit S = {v ∈ V | il existe un chemin de s à v dans Gf } et T = V \S . On a s ∈ S et par hypothèse

t ∈ T donc (S, T ) est une coupe du graphe. Alors ∀(u, v) ∈ S × T, f (u, v) = c(u, v) car sinon on aurait cf (u, v) > 0

2
donc (u, v) ∈ Ef ce qui placerait v dans S . Par (*), on a |f | = c(u, v) = c(S, T ).
P P P P
f (u, v) =
u∈S v∈T u∈S v∈T

(iii) =⇒ (i) : Soit (S, T ) donné par l'hypothèse. Par le lemme, on sait que pour tout ot f˜ de G, on a
|f˜| ≤ c(S, T ) = |f |, donc f est bien de valeur maximale parmi les ots dans G.

Analyse : La correction de l'algorithme de Ford-Fulkerson repose sur le théorème max ow-min cut. Le caractère
naïf de cet algorithme vient du fait que la manière de trouver des chemins augmentants n'est pas explicitement
spéciée. Si le choix des chemins est mauvais, le nombre de tours de boucle de l'algorithme peut être de l'ordre de
|E||f˜| avec |f˜| la valeur d'un ot maximal de G [2]. A titre purement anecdotique et totalement hors du cadre de
cette étude, le choix de chemin par des parcours en largeur (algorithme de Edmonds-Karp) est ecace et confère
une complexité O(|V ||E|2 ).

3 Algorithme de Dinitz

On présente dans cette partie un algorithme plus ecace dans le cadre de notre étude, en introduisant progressi-
vement des concepts de plus en plus complexes.

3.1 L'algorithme
Dénition : Soit (G = (V, E), c, s, t) un réseau, et f un ot dans ce réseau. On pose pour v ∈ V , δ(s, v) la
longueur d'un plus court chemin de s à v dans Gf . On dénit alors le graphe de niveau GL = (V, EL ) avec
EL = {(u, v) ∈ Ef | δ(s, v) = 1 + δ(s, u)}. GL est le graphe résiduel dans lequel on ne garde que les plus courts
chemins depuis s. Notons que GL est un graphe acyclique.

Dénition : Soit (G, c, s, t) un réseau de ot, avec G acyclique. On appelle ot bloquant tout ot f du ré-
seau tel que pour tout chemin p de s à t dans G, il existe un arc (u, v) ∈ p tel que f (u, v) = c(u, v). Autrement
dit, un ot bloquant est un ot saturant tous les chemins de s à t en au moins un arc.

On en déduit un algorithme similaire à celui de Ford et Fulkerson, permettant de calculer des ots maximaux. La
diérence entre les deux algorithmes est que l'algorithme de Dinitz sature simultanément les chemins augmentants
du graphe de même longueur. Ainsi, au cours de l'algorithme, la distance de s à t dans le graphe de niveau augmente
strictement.

Algorithme 2 Algorithme de Dinitz

Entrée: Un réseau (G, c, s, t)
Sortie: Un ot f du réseau vériant |f | maximale
1: pour tout (u, v) ∈ E faire
2: f (u, v) ← 0
3: n pour
4: tant que il existe un chemin de s à t dans GL faire
5: Calculer un ot bloquant f ′ dans (GL , cf , s, t)
6: f ← f + f′
7: n tant que
8: Renvoyer f

Analyse : Comme évoqué précédemment, l'algorithme sature tous les plus courts chemins de s à t dans GL
lors de chaque itération donc la distance δ(s, t) de s à t dans GL augmente strictement à chaque tour de boucle.
Comme δ(s, t) ≤ |V |−1, on eectue O(|V |) tours de boucle. On obtient au passage la terminaison de l'algorithme.
Les instructions des lignes 2 et 6 s'eectuent en O(|E|). Il reste à trouver une manière ecace de calculer des
ots bloquants, an d'estimer la complexité totale de l'algorithme. La correction de l'algorithme repose sur le
théorème max-ow min-cut

3.2 La structure d'arbres dynamiques

An de calculer des ots bloquants ecacement, on introduit la structure d'arbres dynamiques.
La structure d'arbres dynamiques encode ici une forêt d'arbres généraux (c'est à dire sans conditions sur l'arité),
où chaque arête possède un coût réel positif. On doit y eectuer les opérations suivantes :
 root(v) : renvoie la racine de l'arbre contenant le noeud v .
 parent(v) : renvoie le père du noeud v , −1 si v est la racine de l'arbre qui le contient.

3
  cost(v) : renvoie le coût de l'arête (v, parent(v)).
 mincost(v) : renvoie le noeud w le plus proche de la racine tel que cost(w) soit minimal parmi les coûts
des arêtes du chemin de v à root(v).
 link(v, w, c) (nécessite v = root(v)) : crée une arête de coût c reliant v à w, de sorte que w soit le père
de v .
 cut(v) : supprime l'arête (v, parent(v)) si elle existe, et renvoie son coût le cas échéant.
 update(v, x) : ajoute x au coût de chaque arête du chemin de v à root(v).
An d'implémenter ecacement la structure, on partitionne les arêtes en deux catégories : majeures et mineures
[3], de sorte que chaque noeud aie au plus une arête majeure le reliant à l'un de ses ls. On peut voir l'ensemble
des arêtes majeures comme formant un ensemble de chemins à noeuds disjoints, reliés entre eux par les arêtes
mineures (un chemin étant éventuellement réduit à un seul noeud). Un chemin est donc une séquence de noeuds
reliés entre eux par des arêtes majeures. La tête du chemin est dénie comme étant le noeud le plus profond, et la
queue est le noeud le moins profond. On stocke explicitement les informations d'une arête mineure, et on utilise
des chemins pour stocker les informations d'arêtes majeures.

a a

2 5 2 5

b c b c

4 8 4 8

1 3 1 3

e g e g

d f d f

6 6

h h

Figure 2  Un arbre dynamique. En pointillés les arêtes mineures et en trait plein les arêtes majeures. En
couleurs, les chemins.

On ajoute donc une fonction expose(v) qui rend majeures les arêtes du chemin de v à root(v) et mineures
toutes autres les arêtes incidentes à ce chemin, an de préserver la structure de la partition (voir Figure 3). Cette
fonction renvoie le chemin d'arêtes majeures ainsi obtenu. A l'aide de cette fonction, on peut se contenter d'écrire
les opérations simplement sur des chemins, puis pour opérer sur les arbres, d'appliquer la fonction expose et
d'opérer sur le chemin renvoyé.
Le problème est donc réduit à l'élaboration d'une structure de chemin qui permette de réaliser ces opérations.

a a

2 5 2 5

b c b c
expose(f )
4 8 4 8

1 3 1 3

e g e g

d f d f

6 6

h h

Figure 3  L'opération expose. Le chemin bleu est renvoyé.

4
3.3 Une structure de chemin
Dénition : Un chemin est une suite de noeuds, reliés par des arêtes, possédant chacune un coût. On requière
de pouvoir y eectuer les opérations suivantes :
 path(v) : renvoie le chemin contenant le noeud v .
 after(v) : renvoie le noeud situé après v dans le chemin s'il existe.
 before(v) : renvoie le noeud situé avant v dans le chemin s'il existe.
 head(p) ; tail(p) : renvoie respectivement la tête et la queue du chemin p, c'est-à-dire les noeuds situés
le plus à gauche et le plus à droite de p.
 construct(p, q, x) : renvoie le chemin obtenu par la concaténation de p et q en ajoutant une arête de coût
x de p à q .
 split(v) : découpe le chemin contenant le noeud v en au plus 3 morceaux : le sous-chemin p précédant
v (s'il existe), le chemin réduit à v et le sous-chemin q succédant à v (s'il existe). Renvoie le quadruplet
(p, q, x, y) avec x et y les coûts des arêtes maintenant supprimées reliant respectivement p à v et v à q .
 pupdate(p, x) : ajoute x au coût de chaque arête du chemin p.
 pcost(v) : renvoie le coût associé à l'arête (v, after(v)) si elle existe.
 pmincost(p) : renvoie le noeud v le plus proche de la queue tel que pcost(v) soit minimal parmi les coûts
des arêtes du chemin.
Pour implémenter des chemins, on utilise des arbres binaires stricts [3]. Les noeuds internes représentent les
arêtes du chemin, et les feuilles représentent les noeuds du chemin, agencées de gauche à droite suivant l'ordre
d'apparition dans le chemin. Un chemin est donc identié de manière unique par sa racine dans l'arbre binaire.

(b, c)

3 4 5 2
a b c d e (a, b) (d, e)

(c, d)

a b e

c d

Figure 4  Un chemin et une de ses représentations en arbre binaire

On stocke dans un noeud v de l'arbre binaire un booléen ext(v) indiquant si v est externe, pere(v) son père dans
l'arbre binaire (qui vaut −1 si le v est la racine), la tête et la queue du sous-chemin représenté par le sous-arbre
enraciné en v .

Si v est interne, on stocke les ls gauche g(v) et droit d(v) de v . On note c(v) le coût de l'arête représentée par
v et cmin(v) le coût minimal d'une arête du sous-chemin représenté par l'arbre enraciné en v . Alors on stocke
implicitement c(v) et cmin(v) à l'aide de n(v) := c(v) − cmin(v) et nmin(v) := cmin(v) − cmin(pere(v)) si v
n'est pas la racine, et cmin(v) sinon. On peut ainsi accéder à cmin(v), et à c(v) = n(v) + cmin(v) en sommant
nmin(w) pour chaque noeud w du chemin de v à la racine, ce qui prend un temps proportionnel à la profondeur
de v dans l'arbre binaire.
nmin 0 père (b, c) d e queue e
n 0 g (c, d) tête c ext Faux

Figure 5  Les informations stockées dans le noeud interne (d, e) de la Figure 4

Les autres opérations de la structure peuvent être résolues de manière similaire, en remontant le chemin de v à
la racine, voire en O(1) via une information stockée directement dans la racine. Il s'agit donc de maintenir les
arbres équilibrés an que la profondeur d'une feuille soit un O(log(n)) avec n le nombre de noeuds du chemin
associé (qui vaut donc le nombre de feuilles de l'arbre).

Pour équilibrer les arbres, on utilise les rotations gauche et droite sur les arbres binaires, qui permettent de
maintenir la profondeur des feuilles en O(log(n)). On utilise ces rotations pour implémenter construct et split

5
en O(log(n)). On implémente les autres fonctions en O(log(n)) à l'aide de la représentation implicite de c(v) et
cmin(v) et des autres informations stockées dans les noeuds.
On obtient globalement une structure de chemin dont les opérations s'eectuent en O(log(n)), avec n le nombre
de noeuds du chemin.

Complexité : On admet [3] que m opérations sur une structure d'arbres binaires de n noeuds au total s'eec-
tuent avec une complexité O(m log2 (n)). Informellement, le facteur log(n) qui vient s'ajouter à la complexité des
opérations de chemins vient de l'exécution de l'opération expose.

3.4 Le calcul de ots bloquants à l'aide d'arbres dynamiques

Récapitulons les structures employées pour résoudre le problème : on modélisera l'évolution d'un réseau de ot
acyclique par une forêt d'arbres dynamiques. Chacun de ces arbres est réparti en chemins de noeuds disjoints
reliés entre eux par des arêtes mineures. Enn pour représenter un chemin on utilise des arbres binaires équilibrés.

Dans ce qui suit, par souci de clarté, on diérencie un sommet v ∈ V de son noeud ṽ associé dans la forêt.

Le principe de l'algorithme est le suivant [3] : étant donné un réseau (G, c, s, t), on initialise une forêt de |V | arbres
réduits à chaque noeud ṽ pour v ∈ V . On lie ensuite successivement les arbres entre eux pour que le chemin de s̃
à root(s̃) corresponde à un chemin dans le graphe. Dès que root(s̃) = t̃, on a trouvé un chemin de s à t dans
le graphe, qu'il faut donc saturer. On augmente le ot sur ce chemin, et on supprime du graphe les arcs saturés.
On répète cette opération jusqu'à ce qu'il ne reste plus de chemin de s à t. Au cours de l'algorithme, comme on
supprime des arcs, il peut se trouver que dans le graphe, root(s̃) n'aie plus d'arcs sortants. Un tel sommet ne sert
plus à construire de chemin de s à t. On doit donc le supprimer, ainsi que tous les arcs qui lui sont incidents en
tenant compte du ot qui a déjà éventuellement été acheminé dans ces arcs. Voir page suivante pour l'algorithme.

Complexité : Dans l'exécution de l'algorithme, pour chaque arc (v, w) ∈ E , on eectue au plus une fois
link(ṽ, w̃, c(v, w)), puis nécessairement cut(ṽ) une fois, et chacune des autres opérations sur les arbres dy-
namiques O(1) fois. Ainsi on eectue O(|E|) opérations sur les arbres dynamiques, d'où une complexité en
O(|E| log2 |V |).

Correction : Montrons que l'algorithme renvoie bien un ot bloquant. Les lignes 36-38 garantissent l'antisymétrie
car G est acyclique, donc si (u, v) ∈ E , alors (v, u) ∈
/ E.
Les lignes 14, 28, 34 et 37 garantissent la contrainte de capacité, car on a ∀v ∈ V tel que w̃ := parent(ṽ) existe,
0 ≤ cost(ṽ) ≤ c(v, w).
Enn il y a conservation du ot car dès que l'on eectue update(ṽ, −cost(ṽ)) (si v ∈ VP \{s, t}), on a deux cas :
(i) ṽ ∈/ expose(s̃) : alors le ot reste inchangé sur tous les arcs reliés à v donc w∈V f ′ (v, w) est aussi
inchangée.
(ii) ṽ ∈ expose(s̃) : notons w̃ = after(ṽ) et ũ = before(ṽ). Alors implicitement, f ′ (v, w) P sera augmenté
de c, et f ′ (u, v) sera augmenté de c, donc dans la ligne 37, f ′ (v, u) sera baissé de c. Ainsi w∈V f ′ (v, w)
restera inchangée.
Donc l'algorithme renvoie bien un ot.

Enn supposons que le ot f ′ renvoyé ne soit pas bloquant.

Alors on a l'existence d'un chemin s = v0 → v1 → · · · → vn = t dans G tel que ∀i ∈ [[0, n − 1]], on ait
f ′ (vi , vi+1 ) < c(vi , vi+1 ). Comme l'algorithme a terminé, il existe i ∈ [[0, n − 1]], tel que (vi , vi+1 ) a été supprimé
du graphe dans l'exécution de l'algorithme. Soit alors i0 = max{i ∈ [[0, n − 1]] | (vi , vi+1 ) a été supprimé}.
On a i0 ̸= n − 1 car la seule instruction pouvant supprimer un arc de la forme (v, t), est celle de la ligne 27, mais
elle imposerait f ′ (v, t) = c(v, t) ce qui n'est pas le cas pour (vi0 , vi0 +1 ). Ainsi i0 ̸= n − 1, et par le même argument,
la seule instruction qui a pu supprimer (vi0 , vi0 +1 ) est celle de la ligne 12, or si cette instruction a été eectuée,
c'est qu'il n'existe plus aucun arc qui sort de vi0 +1 (ligne 10) donc en particulier, (vi0 +1 , vi0 +2 ) a été supprimé.
Ceci contredit la maximalité de i0 .
Ainsi l'algorithme est correct.

Conclusion : On obtient ainsi par l'analyse précédente que la complexité de l'algorithme de Dinitz est en
O(|E| + |V |(|E| log2 |V | + |E|)) = O(|V ||E| log2 |V |), avec la structure d'arbres dynamiques. Il est bon de noter
que cette complexité est meilleure asymptotiquement que celle évoquée pour l'algorithme de Ford-Fulkerson, mais
la structure étant plus complexe globalement, le calcul de ot maximal pour des petits graphes sera moins ecace
en réalité. Il faut atteindre des graphes de taille assez importante pour que l'algorithme devienne plus ecace.

6
Algorithme 3 Calcul de ot bloquant
Entrée: Un réseau de ot (G = (V, E), c, s, t) avec G acyclique
Sortie: Un ot f ′ bloquant dans G
1: pour tout (u, v) ∈ E faire
2: f ′ (u, v) ← 0
3: n pour
4: pour tout sommet v ∈ V faire
5: Créer un arbre contenant uniquement ṽ
6: n pour
7: tant que il existe un chemin de s à t dans G faire
8: ṽ ← root(s̃)
9: si ṽ ̸= t̃ alors
10: si aucun arc ne sort de v alors
11: (* Il n'existe plus de chemin de v à t : il faut supprimer v *)
12: Supprimer tous les (u, v) ∈ E pour u ∈ V du graphe
13: pour tout ls ũ de ṽ dans l'arbre faire
14: f ′ (u, v) ← c(u, v) − cut(ũ)
15: n pour
16: sinon
17: (* Etendre le chemin *)
18: Choisir w ∈ V tel que (v, w) ∈ E
19: Eectuer link(ṽ, w̃, c(v, w))
20: n si
21: sinon
22: (* Augmenter le ot le long du chemin de s à t exhibé, puis supprimer les arcs saturés *)
23: ṽ ← mincost(s̃)
24: update(s̃, −cost(ṽ))
25: tant que cost(ṽ) = 0 faire
26: w̃ ← parent(ṽ)
27: Supprimer du graphe l'arc (v, w)
28: f ′ (v, w) ← c(v, w) − cut(ṽ)
29: ṽ ← mincost(s̃)
30: n tant que
31: n si
32: n tant que
33: pour tout v ∈ V tel que w̃ := parent(ṽ) existe faire
34: f ′ (v, w) ← c(v, w) − cut(ṽ)
35: n pour
36: pour tout (u, v) ∈ E faire
37: f ′ (v, u) ← −f ′ (u, v)
38: n pour
39: Renvoyer f ′

4 Annexe

4.1 Code Python : chemins

1 class Dpath:
2 def __init__(self,na,nb,cost,ext,p,tag):
3 if ext:
4 [Link] = tag
5 [Link] = True
6 [Link] = p
7 [Link] = float('inf')
8 [Link] = self
9 [Link] = self
10 [Link] = 1
11 else:
12 [Link] = [Link] + [Link]
13 [Link] = False

7
14 [Link] = -1
15 if [Link]:
16 if [Link]:
17 [Link] = cost
18 else:
19 [Link] = min(cost,[Link])
20 [Link] = [Link] - [Link]
21 else:
22 if [Link]:
23 [Link] = min(cost,[Link])
24 [Link] = [Link] - [Link]
25 else:
26 [Link] = min(cost,[Link],[Link])
27 [Link] = [Link] - [Link]
28 [Link] = [Link] - [Link]
29 [Link] = cost - [Link]
30 [Link] = na
31 [Link] = nb
32 if [Link]:
33 [Link] = na
34 else:
35 [Link] = [Link]
36 if [Link]:
37 [Link] = nb
38 else:
39 [Link] = [Link]
40 [Link] = self
41 [Link] = self
42
43 def path(self):
44 """renvoie le chemin associé à un arbre"""
45 if [Link] == -1:
46 return self
47 else:
48 return [Link]()
49 def head(self):
50 """renvoie la tête du chemin associé, doit être appliqué à path(self)"""
51 return [Link]
52 def tail(self):
53 """renvoie la queue du chemin associé, doit être appliqué à path(self)"""
54 return [Link]
55 def before(self):
56 """renvoie le sommet situé avant celui passé en argument dans le chemin associé, erreur
,→ s'il n'existe pas"""
57 if not [Link]:
58 if [Link] == -1:
59 return -1
60 else:
61 if [Link] == self: #si le sommet self est à droite de son parent
62 return self
63 else:
64 return [Link]()
65 else:
66 if [Link] == self: #si le sommet self est à droite de son parent
67 u = self
68 else:
69 u = [Link]()
70 assert u != -1 , "Pas de prédécesseur"
71 return [Link]
72 def after(self):
73 """renvoie le sommet situé après celui passé en argument dans le chemin, erreur s'il
,→ n'existe pas"""
74 if not [Link]:
75 if [Link] == -1:
76 return -1

8
 77 else:
78 if [Link] == self: #si le sommet self est à gauche de son parent
79 return self
80 else:
81 return [Link]()
82 else:
83 if [Link] == self: #si le sommet self est à gauche de son parent
84 u = self
85 else:
86 u = [Link]()
87 assert u != -1 , "Pas de successeur"
88 return [Link]
89 def pcost(self):
90 """renvoie le cout de l'arc (v,after(v)) du chemin associé"""
91 if not [Link]:
92 if [Link] == -1:
93 return -1,[Link],0
94 else:
95 u,grossmin,gross_u = [Link]()
96 if [Link] == self: #si le sommet self est à gauche de son parent
97 return self, grossmin + [Link], grossmin
98 else:
99 return u, grossmin + [Link], gross_u
100 else:
101 u,grossmin,gross_u = [Link]()
102 if [Link] == self: #si le sommet self est à gauche de son parent
103 u = self
104 gross_u = grossmin
105 if u == -1: #pas de successeur
106 return None
107 else:
108 return [Link] + gross_u
109 def pmincost(self):
110 """renvoie le sommet v le plus proche de la queue tq pcost(v) soit minimal parmi les couts
,→ du chemin, doit être appliqué à path"""
111 u = self
112 while [Link] != 0 or ((not [Link]) and [Link] <= 0):
113 if (not [Link]):
114 u = [Link]
115 else:
116 u = [Link]
117 v = [Link]
118 if [Link]:
119 return v
120 else:
121 return [Link]
122 def pupdate(self,x):
123 """ajoute x à toutes les arêtes du chemin associé, doit être appliqué à path"""
124 [Link] += x
125 def destroy(self):
126 """renvoie les deux arbres issus de la destruction de la racine self d'un arbre"""
127 na,nb = [Link],[Link]
128 [Link] = -1
129 [Link] = -1
130 if [Link]:
131 if [Link]:
132 pass
133 else:
134 [Link] = [Link] + [Link]
135 else:
136 if [Link]:
137 [Link] = [Link] + [Link]
138 else:
139 [Link] = [Link] + [Link]
140 [Link] = [Link] + [Link]

9
141 return na,nb,[Link] + [Link]
142 def rot_g(self):
143 """performe une rotation gauche en self, nécessite l'existence d'un noeud interne fils
,→ droit de self"""
144 assert not [Link], "Noeud non interne"
145 assert not [Link], "Fils droit non interne"
146 u = self
147 v = [Link]
148 p = [Link]
149 q = [Link]
150 r = [Link]
151 [Link] = [Link]
152 if [Link] != -1:
153 if [Link] == u:
154 [Link] = v
155 else:
156 [Link] = v
157 [Link] = v
158 [Link] = u
159 [Link] = q
160 [Link] = u
161 nu = [Link]
162 ncu,ncv = [Link],[Link]
163 nv,np,nq,nr = [Link],[Link],[Link],[Link]
164 [Link] = min(np,nq+nv,ncu)
165 [Link] = nu
166 [Link] = nr+nv
167 [Link] = np - [Link]
168 [Link] = nq + nv - [Link]
169 [Link] = ncv + nv
170 [Link] = ncu - [Link]
171 [Link] = [Link]
172 if [Link]:
173 [Link] = q
174 else:
175 [Link] = [Link]
176 return v
177 def rot_d(self):
178 """performe une rotation droite en self, nécessite l'existence d'un noeud interne fils
,→ gauche de self"""
179 assert not [Link], "Noeud non interne"
180 assert not [Link], "Fils gauche non interne"
181 u = self
182 v = [Link]
183 r = [Link]
184 q = [Link]
185 p = [Link]
186 [Link] = [Link]
187 if [Link] != -1:
188 if [Link] == u:
189 [Link] = v
190 else:
191 [Link] = v
192 [Link] = v
193 [Link] = u
194 [Link] = q
195 [Link] = u
196 nu = [Link]
197 ncu,ncv = [Link],[Link]
198 nv,np,nq,nr = [Link],[Link],[Link],[Link]
199 [Link] = min(np,nq+nv,ncu)
200 [Link] = nu
201 [Link] = nr+nv
202 [Link] = np - [Link]
203 [Link] = nq + nv - [Link]

10
204 [Link] = ncv + nv
205 [Link] = ncu - [Link]
206 [Link] = [Link]
207 if [Link]:
208 [Link] = q
209 else:
210 [Link] = [Link]
211 return v
212 def split(self):
213 """Doit être appliqué en un sommet externe. Renvoie les arbres associés aux sous-chemins
214 précédant et succédant au sommet self ainsi que les coûts des arêtes supprimées"""
215 assert [Link] ,"Sommet non externe"
216 if [Link] == -1:
217 return -1,-1,None,None
218 L = [self]
219 while L[-1].bparent != -1:
220 [Link](L[-1].bparent)
221 n = len(L)
222 for i in range(n-2,0,-1):
223 v = L[i]
224 if [Link] == v:
225 s = [Link].rot_d()
226 elif [Link] == v:
227 s = [Link].rot_g()
228 L = [self]
229 while L[-1].bparent != -1:
230 [Link](L[-1].bparent)
231 n = len(L)
232 for i in range(n-2,0,-1):
233 v = L[i]
234 if [Link] == v:
235 s = [Link].rot_d()
236 elif [Link] == v:
237 s = [Link].rot_g()
238 na,nb,c = [Link]().destroy()
239 if self == na:
240 return -1,nb,None,c
241 elif self == nb:
242 return na,-1,c,None
243 elif [Link] == na:
244 nc,t,x = [Link]()
245 return nc,nb,x,c
246 elif [Link] == nb:
247 t,nc,x = [Link]()
248 return na,nc,c,x
249
250
251
252 def construct(p,q,x):
253 """p et q chemins, construit le chemin obtenu en reliant tail(p) à head(q) par une arête de
,→ coût x"""
254 return Dpath(p,q,x,False,-1,0)
255
256
257 def affiche_chemin(c):
258 if c == -1:
259 return None
260 if [Link]:
261 print([Link])
262 return None
263 def aux(p):
264 if [Link]:
265 print([Link],end = ' ')
266 c = [Link]()
267 if c != None:

11
 268 print('-'+str(c)+'>', end = ' ')
269 else:
270 aux([Link])
271 aux([Link])
272 aux(c)
273
274 def sommet(tag):
275 return Dpath(0,0,0,True,-1,tag)

4.2 Code Python : arbres dynamiques

1 DTree = {}
2 def som(tag):
3 s = sommet(tag)
4 DTree[s] = (-1,None)
5 return s
6 def splice(p):
7 v,c = DTree[[Link]()]
8 assert v != -1, 'Appel sur le sommet'
9 q,r,x,y = [Link]()
10 if q != -1:
11 DTree[[Link]()] = v,x
12 p = construct(p,[Link](),c)
13 if r == -1:
14 return p
15 else:
16 return construct(p,r,y)
17 def expose(v):
18 q,r,x,y = [Link]()
19 if q != -1:
20 DTree[[Link]()] = v,x
21 if r == -1:
22 p = [Link]()
23 else:
24 p = construct([Link](),r,y)
25 while DTree[[Link]()][0] != -1:
26 p = splice(p)
27 return p
28 def parent(v):
29 if v == [Link]().tail():
30 return DTree[v][0]
31 else:
32 return [Link]()
33 def root(v):
34 return expose(v).tail()
35 def cost(v):
36 if parent(v) == -1:
37 return None
38 if v == [Link]().tail():
39 return DTree[v][0]
40 else:
41 return [Link]()
42 def mincost(v):
43 if parent(v) == -1:
44 return None
45 return expose(v).pmincost()
46 def update(v,x):
47 expose(v).pupdate(x)
48 def link(v,w,x):
49 construct([Link](),expose(w),x)
50 def cut(v):
51 t = expose(v)
52 p,q,x,y = [Link]()
53 DTree[v] = -1,None
54 return y

12
4.3 Code Python : Ford-Fulkerson
1 def graphe_residuel(G,f):
2 """Construit le graphe résiduel Gf de G pour f, G graphe représenté par matrice d'adjacence et
,→ f flot, aussi représenté par une matrice"""
3 n = len(G)
4 Gf = [[0]*n for _ in range(n)]
5 for i in range(n):
6 for j in range(n):
7 if i == j:
8 Gf[i][j] = 0
9 elif G[i][j] > f[i][j]:
10 Gf[i][j] = G[i][j] - f[i][j]
11 return Gf
12 def chemin(G,s,t):
13 """Effectue un parcours en profondeur pour trouver un chemin de s à t
14 G donné par matrice d'adjacence"""
15 n = len(G)
16 deja_vu = [False]*n
17 deja_vu[s] = True
18 def pp(u):
19 if u == t:
20 return True,[t]
21 deja_vu[u] = True
22 for v in voisins(G,u):
23 if not deja_vu[v]:
24 b,P = pp(v)
25 if b:
26 [Link](u)
27 return b,P
28 return False,[]
29 b,P = pp(0)
30 if b:
31 [Link]()
32 return b,P
33 return False,[]
34 def cap_chemin(Gf,p):
35 """Calcule la capacité résiduelle d'un chemin p"""
36 c = inf
37 for i in range(len(p)-1):
38 u = Gf[p[i]][p[i+1]]
39 if u < c:
40 c = u
41 return c
42 def ford_fulk_naif(G,s,t):
43 """Utilise le parcours en profondeur"""
44 t1 = time()
45 n = len(G)
46 f = [[0]*n for _ in range(n)]
47 Gf = graphe_residuel(G,f)
48 b,p = chemin(Gf,s,t)
49 iterations = 0
50 while b:
51 print(p)
52 iterations += 1
53 cf = cap_chemin(Gf,p)
54 for i in range(len(p)-1):
55 u,v = p[i],p[i+1]
56 f[u][v] = f[u][v] + cf
57 f[v][u] = -f[u][v]
58 Gf = graphe_residuel(G,f)
59 b,p = chemin(Gf,s,t)
60 t2 = time()
61 return f

13
4.4 Code Python : Dinitz
1 def blocking_flow(G,s,t,f,D):
2 """Prend en entrée un graphe G sous forme de listes d'adj, une source s, un puits t, un flot
,→ f, et D : G comme dico
3 Augmente f d'un flot bloquant pour G"""
4 sommets = {}
5 indices = {}
6 som_supp = {}
7 arc_supp = {}
8 fils = {}
9 for i in range(len(G)):
10 sommets[i] = som('v'+str(i)) # Création d'une forêt contenant des arbres réduits à chaque
,→ sommet du graphe
11 indices[sommets[i]] = i
12 fils[sommets[i]] = {}
13 b = True
14 som_s = sommets[s]
15 som_t = sommets[t]
16 while b:
17 v = root(som_s)
18 vi = indices[v]
19 if v == som_t: # On a trouvé un chemin de s à t
20 u = mincost(som_s)
21 c = cost(u)
22 update(som_s,-c)
23 u = mincost(som_s)
24 while u != None and cost(u) == 0: # Suppression de tous les arcs saturés
25 p = parent(u)
26 f[indices[u]][indices[p]] += D[indices[u]][indices[p]]
27 arc_supp[(u,p)] = None
28 fils[p].pop(u,None)
29 cut(u)
30 u = mincost(som_s)
31
32 else: # On n'a pas encore de chemin jusqu'à t
33 if G[vi] == []: # Plus aucun sommet ne quitte v, il faut l'enlever du graphe
34 if v == som_s: # Plus aucun chemin de s à t
35 b = False
36 else: # Plus aucun chemin de v à t : supprimer v
37 som_supp[v] = None
38 for u in fils[v].keys():
39 f[indices[u]][indices[v]] += D[indices[u]][indices[v]] - cut(u)
40 fils[v] = {}
41 else: # Etendre le chemin
42 b2 = True
43 w = sommets[G[vi][-1][0]]
44 while (v,w) in arc_supp or w in som_supp:
45 G[vi].pop()
46 if G[vi] == []:
47 b2 = False
48 break
49 w = sommets[G[vi][-1][0]]
50 if b2:
51 link(v,w,G[vi][-1][1])
52 fils[w][v] = None
53 for i in range(len(G)):
54 v = parent(sommets[i])
55 if v != -1:
56 f[i][indices[v]] += D[i][indices[v]] - cut(sommets[i])
57
58
59
60
61

14
 62 def dico(G):
63 D = {}
64 for i in range(len(G)):
65 D[i] = {}
66 for c in G[i]:
67 D[i][c[0]] = c[1]
68 return D
69
70 def calc_gl(G,s,t,f):
71 GL = [[] for _ in range(len(G))]
72 F = deque([s])
73 d = [inf]*len(G)
74 d[s] = 0
75 while len(F) > 0:
76 u = [Link]()
77 for c in G[u]:
78 v,x = c
79 if d[v] == inf and x > f[u][v]:
80 GL[u].append((v,x-f[u][v]))
81 d[v] = d[u]+1
82 [Link](v)
83 elif d[v] == d[u]+1 and x > f[u][v]:
84 GL[u].append((v,x-f[u][v]))
85 return GL,d[t] != inf
86
87
88 def dinitz(G,s,t):
89 f = {}
90 for i in range(len(G)):
91 f[i] = {}
92 for c in G[i]:
93 f[i][c[0]] = 0
94 Gl,b = calc_gl(G,s,t,f)
95 while b:
96 D = dico(Gl) # en O(|E|)
97 blocking_flow(Gl,s,t,f,D) # en O(|E|log²|V|)
98 Gl,b = calc_gl(G,s,t,f) # en O(|E|)
99 return f

4.5 Bibliographie
[1] [Link]
[2] Introduction to Algorithms, Ed.2, Ch.26, T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein.
[3] A Data Structure for Dynamic Trees, D.D. Sleator, R.E. Tarjan

15