Algorithmes

 et  Graphes  

Loïc  Hélouët  
 
[Link]@[Link]  
 Plan  
1.   Defini?ons  de  base  
2.   Parcours    
1.   en  largeur  
2.   en  profondeur  
3.   Arbres  couvrants  :  Kruskal  et  Prim  
4.  Plus  courts  chemins  
5.  Dijkstra  
6.  Bellman-­‐Ford  
7.  Floyd  Warshall  
8.  Johnson  
3.   Flot  Maximal  :  Ford  Fulkerson  
4.  Connexité  :  
1.  Recherche  de  cycles  :  Tiernan  
2.  Composantes  connexes  :  Tarjan  
 Defini?ons  
Definition 1 : Un graphe non- orienté est un couple G=(V,E) dans lequel
V est un ensemble de sommets
E ⊆ V x V est un ensemble d arêtes

Definition 2: Un graphe orienté est un couple (V,A) dans lequel

V est un ensemble de sommets
A ⊆ V x V est un ensemble d arêtes

Definition 3: Un graphe pondéré est un graphe dans lequel

chaque arête (arc) possède un poids (réel)
c: A ℜ
Definition 4 Un chemin dans un graphe est une séquence ρ = s0.s1 … sk telle que
(si , si+1) est une arête (resp. un arc) de G. Un chemin ρ est un cycle ssi
s0 = sk

Le poids d un chemin ρ = s0.s1 … sk est : ∑ c( s , s

i∈0.. k −1
i i +1 )
 Défini?ons  
s2
s0 s2
s0

s3
s1 s3
s1
Exemple de graphe
Exemple de graphe orienté
3.5
s2
s0
2
9.1
10
Poids(s0.s1.s0.s1.s3) = 35.2
s3
s1 7
Exemple de graphe orienté et pondéré
 Defini?ons  
Definition 5 : Un successeur d un sommet x dans un graphe G=(V,E) (resp G=(V,A))
est un sommet y tel que (x,y) ∈ E (resp (x,y) ∈ A)

Definition 6: Le degré d un sommet est le nombre de ses successeurs. Le degré d un

graphe est le degré maximal de ses sommets

Definition 7: Un graphe pondéré est un graphe dans lequel

chaque arête (arc) possède un poids (réel)

Definition 8: Un chemin hamiltonien est un chemin de G qui passe une et une seule
fois par tous ses sommets de G. G est un graphe hamiltonien s il possède
un cycle passant par tous ses sommets une et une seule fois

Définition 9: deux sommets x et y sont à distance k si le plus court chemin

allant de x à y comporte k arcs
 Représenta?on  
Représentation Matricielle
s2
s0
0 1 2 3
0 F T T F
1 T F T F
2 F F T T s3
s1
3 F F F F

0 1 2 3 3.5 s2
s0
0 -1 9.1 3.5 -1
2
9.1
1 10 -1 -1 7 10
s3
2 -1 -1 -1 2 s1 7
3 -1 -1 -1 -1 Espace utilisé Θ(n2)
 Représenta?on  
Représentation par liste
d adjacence s2
s0

0 1 2
s3
1 0 1 s1

2 2 3

Espace utilisé Θ(n+p)

 Parcours  
Parcours en profondeur d abord

Choisir un sommet de départ, et suivre un chemin aussi loin que possible en

marquant les sommets, et sans repasser par un sommet marqué.
Lorsqu un sommet marqué est atteint, le parcours reprend au dernier choix

Procedure Profondeur (G, s )

Marque:tableau[1..n] de booleens

Pour i dans 1..n faire

marque[i]:=faux
finpour
Pour i dans 1..n faire
si marque[i]:=faux alors
prof(i,G,marque)
finsi
finpour
 Parcours  

Procedure prof (s:entier,

G:Graphe, M:tableau[1..n] de booleens)
Var j,v: entiers /* sommets */

M[s] := vrai
Pour j dans 1.. Degré(s) faire
v:= jeme successeur de s
Si M[v]=faux alors prof(v,G,M) finsi

finpour
 Parcours  
(Version matricielle)

Procedure prof (s:entier,

G:Graphe, M:tableau[1..n] de booleens)
Var j: entiers /* sommets */

M[s] := vrai
Pour j dans 1..n faire
si G[s,j]=vrai et M[j]=faux alors
prof(j,G,M)
finsi
finpour
 Parcours  

3
1 8 1
9
1 6
3 7
4 1
2
s 3
4 2
1 2
1 2
5 1

1
1
 Parcours  
Parcours en largeur d abord

Choisir un sommet de départ s, et visiter tous ses successeurs avant de visiter

les autres descendants.
Le parcours en largeur visite les sommets à distance 1 de s
puis les sommets à distance 2,
….
 Parcours  
Parcours en largeur d abord

Procedure larg(s: entier, G: graphe,

M: tableau [1..n] d entiers)

Var, v,w,i : entiers, F: file

F:= file vide

M[s]:= vrai
F:= ajouter(F,s)
Tant que (non vide(F)) faire
v:= premier(F)
pour i dans 1.. Degré(v) faire
w= ieme successeur de v
si M[w] = faux alors
M[w] := vrai
F:= ajouter(F,w)
finsi
finpour
Fintantque
 Parcours  

7
1 9 1
3
1 8
3 6 1
4
s 2 3
2 4
1 2
1 2
5 1

1
1
 Parcours  
Algorithmes de base

n  pour les graphes : Tarjan, Tiernan

n  pour la résolution de problèmes dont
l espace de solutions se représente comme un graphe
ex : algos gloutons

Largeur ou profondeur : O(|V| +|A|) (avec les bonnes structures de données)

Lequel choisir ?

dépend de la structure du graphe et de la nature du problème

à résoudre
 Arbres  Couvrants  

Definition : Un arbre couvrant d un graphe G=(V,E) est

un sous-graphe G=(V,E ) tel que

n  G est un arbre

n  E ⊆ E

Le poids d un arbre couvrant est défini par

W= ∑ M [i, j]
i , j∈E '
 Arbres  couvrants  
4  
9  
Arbre  couvrant  minimal  :   1   4  
  9   5  
6   2  
G  :  graphe     4   7   3  
n connexe   2   9  
3  
n valué   8   10  
n non  orienté  
9  
  9  
Trouver  un  ensemble  d arrêtes:   9   8  
  18  
n   connectant  tous  les  sommets  
n   de  poids  minimal  

Algorithme  de  Prim  :  

 Choisir  un  sommet  arbitraire  
 faire  croitre  un  arbre  à  par?r  de  ce  sommet  
 de  la  manière  la  plus  économique  possible  
 Arbres  couvrants  
Algorithme  de  Prim  [Froidevaux]  
 
Procedure Prim(s,G)

entier s; /* sommet initial*/

graph G =(S,A,C) /*sommets/arrêtes/cout*/

Variables :

graph T /* l abre en construction*/

int i, m, y ;
real : v ;
Set : M /* sommets non étudiés*/
int closer[1..N] /* plus proche sommet de T*/
real d[1..N] /* plus petite distance entre
un sommet et un sommet de l arbre*/

 
 Arbres  couvrants  
Algorithme  de  Prim  (suite)   T := graphe_vide!
M := ensemble_vide !
  Pour i= 0 jusqu'à N Faire !
!d[i] := coût(s, i, G) /* ∝ si pas d arc */!
!closer[i] := s !
!M := Ajouter (i,M) !
Fin pour !
!
M := Supprimer (s,M) /* s = sommet de départ */!
!
Tant que M <> Ensemble_vide Faire !
!m := Choisir_min(M,d)!
!M := Supprimer (m,M) !
!z := closer[m] !
!v := coût (m,z,G) !
!T := Ajout arête <m,z> de coût v à T !
!Pour tout y successeur de m dans G !
! !Si y∈M et (cout(m,y,G) < d[y]) alors !
! ! !d[y] := coût(m,y,G) !
! ! !closer[y] := m !
! !Fin Si !
!Fin Pour !
Fin Tant que!
 4  
9  
1   4  
9   5  
6   2  
4   7   3  
3   2   9  
8   10  
9  
9  
9   8  
18  
 4  
9  
1   4  
9   5  
6   2  
4   7   3  
3   2   9  
8   10  
9  
9  
9   8  
18  
 4  
9  
1   4  
9   5  
6   2  
4   7   3  
3   2   9  
8   10  
9  
9  
9   8  
18  
 4  
9  
1   4  
9   5  
6   2  
4   7   3  
3   2   9  
8   10  
9  
9  
9   8  
18  
Etc…
 Arbres  couvrants  
Prim fonctionne par parcours de l arbre en choisissant
les poids minimum

Complexité : O( |V| x |E| )

M,d,closer modélisent en fait un ensemble d arrêtes.

Chaque arrête ne peut être choisie qu une fois

Pour chaque nouvelle arrête ajoutée, on recherche de nouveaux

successeurs (au plus |V| )

Peut être amélioré en O( |E| x log(|V|) ) si

M est modélisé par un tas
 Arbres  couvrants  

Algorithme de Kruskal [Froidevaux]

Utilisation d un tableau

comp[1..n] pour représenter les composantes connexes

Comp[i].repr = représentant de la composante connexe du sommet i

(sommet de plus petit numéro)

Comp[i].card = cardinal de la composante

 Arbres  Couvrants  
Par union de composantes connexes : Kruskal
Procedure Union(x,y: entiers; /* des numéros de sommets */
Var comp tableau[1..n] de structure repr, card
Var j1,j2,k: entiers;

j1:= comp[x].repr ; j2:= comp[y].repr

Si comp[j1].card > comp[j2].card alors
pour k dans 1 à n faire
si comp[k].repr = j2 alors comp[k].repr:=j1
finsi
finpour
comp[j1].card := comp[j1].card + comp[j2].card

sinon
pour k dans 1 à n faire
si comp[k].repr = j1 alors comp[k].repr:=j2
finpour
comp[j2].card := comp[j2].card + comp[j1].card
finsi
 Arbres  Couvrants  
Algorithme de Kruskal
Procedure Kruskal (Graphe G, Graphe T)
/* S = sommets de G */
/* cout : fonction de cout des arcs */

Var comp : tableau[1..n] de structure repr, card : 1..n

i: entiers; x,y: entiers /* sommets */

T:= graphe vide

Pour i dans 1 à n faire ajouter un sommet à T finpour
U:=A
Pour i dans 1 à n faire /* autant de composantes que de sommets */
comp[i].repr=i
comp[i].card=1
finpour
i:=1
Tant que i<n faire
{x,y}:=min(U); U := supprimer({x,y},U)
si comp[x].repr <> comp[y].repr alors
union(x,y,comp)
T:= ajouter_arrête {x,y} à T
i:=i+1
finsi
fintantque
 4  
9
9  
7 7   4  
4 9   5  
6   2   8
4   7   3  
6
3   2   9  
1
3 8   10   10
9  
9   5
9   8  
18  

2
 4  
9
9  
7 7   4  
4 9   5  
6   2   8
4   7   3  
3
3   9  
1
3 8   10   10
9  
9   5
9   8  
18  
T=
6  
2 3  
 4  
9
9  
7 7   4  
3 9   5  
6   8
4   7   3  
3
3   9  
1
3 8   10   10
9  
9   5
9   8   4  
18  
T=
6  
2 3  
 4  
9
9  
7 7   4  
3 9   5  
6   8
4   7  
3
3   9  
1
3 8   10   8
9  
8  
9   5
9   8   4   10  
18  
T=
6  
2 3  
 Arbres  couvrants  
Fonctionnement : par union de composantes connexes

Remarques :
n  Kruskall marche sur des graphes non connexes et calcule alors
une forêt couvrante minimale
n La structure T calculée n est pas connexe à chaque étape, même dans
un graphe connexe

Complexité : Θ(max(n2,m log m ) si matriciel (ou Θ(m. log m) avec L.A.)

-initialisation de T en Θ(n2) (Θ(n))
-initalisation de U en Θ(n2) (Θ(m))
-initialisation de comp en Θ(n)
-min() et supprimer : au pire m fois
le tri de U se fait en Θ(m log m)
- On a un nombre de comparaisons comp[x].repr = comp[x].repr en Θ(m)
- n-1 appels à union(),
et chaque appel coute Θ(n) au pire : Θ(n2) Θ(m)
- ajouter_arête() appelée n fois : Θ(n)
Algo   Complexité   Remarque  
Prim   O(  |V|  x  |E|  )   Arbre  couvrant  
Kruskal   O(|E|.  log  |V|)   Forêt  couvrante  
Ou    
Θ(max(n2,m  log  m  ))  
 Plus  court  chemin  

Variantes

n  Partant d un sommet s, plus court chemin vers un

sommet t
n  Partant d un sommet s, plus court chemin vers tout
autre sommet du graphe
n  Plus court chemin de tout s vers tout t
n  Plus court chemin passant par tous les sommets

Distance exprimée en termes de :

n poids des chemins

n  nombre d arcs (idem poids à 1)
 Plus  court  chemin  
Algorithme de Dijkstra [Cormen]

Partant d un sommet s, plus court chemin vers un sommet t

Dijkstra (G:graphe, sdeb:entier)

Initialisation (D : matrice 1..n d entiers)

Pour i dans 1.. N faire

D[i] = ∝
Finpour
d[sdeb] := 0

/* D[i] = distance de sdeb à si */

 Plus  court  chemin  
Partant d un sommet s, plus court chemin vers un sommet t

Mise_à_jour (D: tableau 1.. D entiers ,

s1: entier,s2:entier)

/* met à jour les distances entre sdeb et s2 */

/* vaut-il mieux passer par s1 ou pas ?*/

Si D[s2] > D[s1] + M[s1,s2] alors

D[s2]:= D[s1] + M[s1,s2]

Finsi
 Plus  court  chemin  
Partant d un sommet s, plus court chemin vers un sommet t

Dijkstra(G,sdeb,sfin)
Var Q : ensemble de sommets

Initialisation(G,sdeb)

Q := ensemble de tous les nœuds

tant que Q n'est pas vide faire

s1 := Trouve_min(Q)
Q := retirer(Q,s1)
pour chaque nœud s2 voisin de s1 faire
maj_distances(s1,s2)
finpour
fintantque
 Plus  court  chemin  
sdeb   2   3   4   5   6   7   8   9   sfin  
0   ∝   ∝   ∝   ∝   ∝   ∝   ∝   ∝   ∝  

4   9
2   7 1   4  
4 Traiter sdeb
9   5  
6   2   8
4   6 7   3  
3   2   9  
sdeb 3 8   10   sfin
9  
9   5
9   8  
18  

2
sdeb   2   3   4   5   6   7   8   9   sfin  
0   9   3   6   ∝   ∝   ∝   ∝   ∝   ∝  
 Plus  court  chemin  
sdeb   2   3   4   5   6   7   8   9   sfin  
0   9   3   6   ∝   ∝   ∝   ∝   ∝   ∝  

4   9
2   7 1   4  
4 Traiter s3
9   5  
6   2   8
4   6 7   3  
3   2   9  
sdeb 3 8   10   sfin
9  
9   5
9   8  
18  

2
sdeb   2   3   4   5   6   7   8   9   sfin  
0   9   3   6   12   5   ∝   ∝   ∝   ∝  
 Plus  court  chemin  
sdeb   2   3   4   5   6   7   8   9   sfin  
0   9   3   6   12   5   ∝   ∝   ∝   ∝  

4   9
2   7 1   4  
4 Traiter s6
9   5  
6   2   8
4   6 7   3  
3   2   9  
sdeb 3 8   10   sfin
9  
9   5
9   8  
18  

2
sdeb   2   3   4   5   6   7   8   9   sfin  
0   9   3   6   12   5   14   ∝   ∝   ∝  
 Plus  court  chemin  
sdeb   2   3   4   5   6   7   8   9   sfin  
0   9   3   6   12   5   14   ∝   ∝   ∝  

4   9
2   7 1   4  
4 Traiter s4
9   5  
6   2   8
4   6 7   3  
3   2   9  
sdeb 3 8   10   sfin
9  
9   5
9   8  
18  

2
sdeb   2   3   4   5   6   7   8   9   sfin  
0   9   3   6   12   5   8   ∝   ∝   ∝  
 Plus  court  chemin  
sdeb   2   3   4   5   6   7   8   9   sfin  
0   9   3   6   12   5   8   ∝   ∝   ∝  

4   9
2   7 1   4  
4 Traiter s7
9   5  
6   2   8
4   6 7   3  
3   2   9  
sdeb 3 8   10   sfin
9  
9   5
9   8  
18  

2
sdeb   2   3   4   5   6   7   8   9   sfin  
0   9   3   6   12   5   8   13   12   ∝  
 Plus  court  chemin  
sdeb   2   3   4   5   6   7   8   9   sfin  
0   9   3   6   12   5   8   13   12   ∝  

4   9
2   7 1   4  
4 Traiter s2
9   5  
6   2   8
4   6 7   3  
3   2   9  
sdeb 3 8   10   sfin
9  
9   5
9   8  
18  

2
sdeb   2   3   4   5   6   7   8   9   sfin  
0   9   3   6   12   5   8   13   12   27  
 Plus  court  chemin  
sdeb   2   3   4   5   6   7   8   9   sfin  
0   9   3   6   12   5   8   13   12   27  

4   9
2   7 1   4  
4 Traiter s5
9   5  
6   2   8
4   6 7   3  
3   2   9  
sdeb 3 8   10   sfin
9  
9   5
9   8  
18  

2
sdeb   2   3   4   5   6   7   8   9   sfin  
0   9   3   6   12   5   8   13   12   22  
 Plus  court  chemin  
sdeb   2   3   4   5   6   7   8   9   sfin  
0   9   3   6   12   5   8   13   12   22  

4   9
2   7 1   4  
4 Traiter s9
9   5  
6   2   8
4   6 7   3  
3   2   9  
sdeb 3 8   10   sfin
9  
9   5
9   8  
18  

2
sdeb   2   3   4   5   6   7   8   9   sfin  
0   9   3   6   12   5   8   13   12   16  
 Plus  court  chemin  
sdeb   2   3   4   5   6   7   8   9   sfin  
0   9   3   6   12   5   8   13   12   16  

4   9
2   7 1   4  
4 Traiter s8
9   5  
6   2   8
4   6 7   3  
3   2   9  
sdeb 3 8   10   sfin
9  
9   5
9   8  
18  

2
sdeb   2   3   4   5   6   7   8   9   sfin  
0   9   3   6   12   5   8   13   12   16  
 Plus  court  chemin  
sdeb   2   3   4   5   6   7   8   9   sfin  
0   9   3   6   12   5   8   13   12   16  

4   9
2   7 1   4  
4 Traiter sfin
9   5  
6   2   8 …. et fin de l algorithme
4   6 7   3  
3   2   9  
sdeb 3 8   10   sfin
9  
9   5
9   8  
18  

2
sdeb   2   3   4   5   6   7   8   9   sfin  
0   9   3   6   12   5   8   13   12   16  
 Plus  court  chemin  
sdeb   2   3   4   5   6   7   8   9   sfin  
0   9   3   6   12   5   8   13   12   16  

On a les distances minimales de sdeb vers tout si… trouver le chemin

A= ε /* mot vide*/
s:= sfin
A:= s. A
Tant que s<> sdeb faire

s:= predecesseur(D,s)
A:= s. A

fait

Predecesseur(D,s) = s ∈V, D[s ]+M[s,s ] =D[s]

 Plus  court  chemin  
Restriction : application à un graphe connexe dont les poids sont positifs
ou nuls

Complexité : en O(n2)

n  A chaque étape, on regarde un sommet de G : n itérations

n  Dans chaque itération, on regarde le sommet avec la plus petite

distance temporaire. Au pire en O(n)

n  puis on met a jour la distance : au pire en O(n)

Soit un algorithme en O(n2)

 Plus  court  chemin  
Preuve de l algorithme
A chaque étape de l algorithme, on peut faire correspondre
un sous graphe de G, dans lequel apparaissent les chemins
de poids minimum de sdeb vers tous les sommets explorés

En ajoutant un sommet, on regarde s il connecte de manière plus

optimale ses successeurs.
4   9
2   7 1   4  
4 9  
6   8
4   6 7   3  
3   2   9  
sdeb 3 8   sfin
9   5
9  

2
 Plus  court  chemin  
Preuve de l algorithme

A chaque étape, les sommets découverts sont à distance

optimale dans le sous-graphe découvert.

Si on ajoute un sommet si, il est forcément « plus loin » de sdeb que tous les
sommets déjà explorés, et tout chemin de sdeb vers un sj déjà exploré passant
par si est de poids supérieur au d(sdeb,si) déjà connu, et donc de poids inférieur
(car tous les poids des arcs sont positifs)

Donc :
une fois un sommet étudié, sa distance ne change plus
lorsque sj est étudié après si, sj est plus loin de sdeb que si

sdeb   3   6   4   7   2   5   9   8   sfin  
0   3   5   6   8   9   12   12   13   16  
 Plus  court  chemin  

Algorithme de Bellman- Ford

Permet de chercher le plus court chemin depuis un sommet source s donné

dans un graphe orienté (à poids)

Autorise certains arcs négatifs.

Complexité en O(|V| x |A| )

 Plus  court  chemin  
booléen Bellman_Ford(G, s)
Poids : tableau[1..n] d entiers
Pred : tableau [1..n] d entiers
i:entier

Poids[1] =0
Pour i dans 2..n faire poids[i] = ∝ finpour

pour i=1 jusqu'à n-1 faire

pour chaque arc (u, v) du graphe faire
paux := poids(u) + poids(arc(u, v))
si paux < poids(v) alors
pred(v) := u;
poids(v) := paux;
finsi
finpour
finpour
pour chaque arc (u, v) du graphe faire
si poids(u) + poids(arc(u, v)) < poids(v) alors
retourner vrai
finsi
finpour

retourner faux
 Plus  court  chemin  

Bellman- Ford retourne …. Vrai ou faux !!? ?? !

Vrai : il existe un circuit de poids négatif

les distances calculées ne sont pas bonnes

Faux : pas de circuit de poids négatif

d[v] est le poids du plus court chemin de s à v

Le chemin est contenu dans le tableau pred
 Plus  court  chemin  

Algorithme de Floyd-Warshall (Roy-Floyd/ Roy Warshall)

Algoritme cubique permettant de calculer la distance des plus

courts chemins entre toute paire de sommets

procedure FloydWarshall (G : matrice )

W:=G
pour k dans 1 .. n faire
pour i dans 1..n faire
pour j dans 1.. n faire
W[i,j] := min(W[i,j], W[I,k]+W[k,j])
fpour
fpour
fpour
 Plus  court  chemin  

Restriction : pas de cycles de poids négatif

Basé sur l observations que tout chemin minimal de i vers j

n  n emprunte pas k, ou

n  emprunte exactement une fois k, et est donc

n la concaténation de chemins de i vers k et de k vers j

Complexité en O(|V|3)
 Plus  court  chemin  
Algorithme de Johnson :

Plus court chemin entre toute paire de sommets

Principe : repondérer les arcs

Utilise à la fois Diskstra et Bellman-Ford comme sous-programmes

Si tous les poids de G sont >0, alors on peut trouver toutes les distances de
sommet à sommet en exécutant |V| fois Dijkstra

Si G contient des arcs de poids négatif, repondérer pour pouvoir utiliser

la même méthode.
 Plus  court  Chemin  
Soit G=(V,A) et w : VxV à R une fonction associant un poids à tout arc de G

On cherche w : VxV à R telle que

1) pour tout (u,v) ∈ A, w (u,v) ≥ 0

2) si p est un plus court chemin de u à v dans G pour w, alors

p est un plus court chemin de u à v dans G pour w

En particulier, on va chercher une focntion h assaociant un réel

A chaque sommet.

Pour chaque (u,v) ∈ A, w (u,v) = w(u,v) + h(u) – h(v)

Propriété : G contient un cycle de poids négatif pour w si et seulement si

G contient un cycle de poids négatif pour w .
 Plus  court  chemin  

Construire G (S ,A ) avec

S =S ∪ { s }
A = A ∪ { (s,v) | v ∈ S }

w(s,v) =0

Ne modifie ni les circuits, ni les plus courts chemin ne contenant pas s

Si G et G ne contiennent pas de circuits négatifs, on choisit

h(v) = δ(s,v)
Ou δ(s,v) est le poids du plus court chemin de s à v
 Plus  court  chemin  

Propriété : Si G ne contient aucun circuit de poids négatif,

alors pour tout u,v
w (u,v) est définie
w (u,v) ≥ 0

Propriété :

Soit p un chemin de v0 à vk
alors w(p) = δ(v0, vk) si et seulement si w (p) = δ (v0, vk)
 Plus  court  chemin  

Johnson(G)
Calculer G =(S ,A )
Si Bellman-Ford (G ,w,s) alors
afficher « Circuit négatif »
Sinon
pour chaque sommet v de G faire
h(v) = δ(s,v) /* calculé par Bellman Ford */
finpour
pour chaque arc (u,v) ∈ A faire
w (u,v) := w(u,v)+h(u)-h(v)
finpour
pour chaque sommet u ∈ S
executer Dijkstra(G,w ,u)
(donne δ (u,v) pour tout v ∈ S )
pour chaque sommet v ∈ S faire
D[u,v] := δ (u,v) + h(v) - h(u)
finpour
finpour
 Plus  court  chemin  

Algorithme de Johnson

Permet de calculer le plus court chemin entre toute paire de sommets

Complexité en O( |V|2 x log(|V|)+ |V| x |A| )

Soit une amélioration par raport à Floyd-Warshall O(|V| 3)

si le graphe est peu dense
 Plus  court  chemin  

Diskstra   O(|V|2)   Pcc  de  s  à  tout  chemin    

Pas  d arcs  néga?fs  
 
Bellman-­‐Ford   O(|V|  x  |A|  )   Pcc  de  s  à  tout  chemin    
Pas  de  cycles  néga?fs  
 
Floyd  Warshall   O(|V|3)   Pcc  entre  toute  paire  de  
sommets    
Pas  de  cycles  néga?fs  
Johnson   O(  |V|2  x  log  |V|  +  |V|x| Pcc  entre  toute  paire  de  
A|  )   sommets    
Pas  de  cycles  néga?fs  
 
 Flot  Maximal  
Problème : Dans un réseau possédant une source s et une
sortie t, trouver le débit maximum de la source vers la sortie.

Applications pratiques :

Problèmes de transports (marchandise, fluide, énergie) dans un

réseau représentable par un graphe dont les nœuds
représentent de points de passage sans stockage et les arcs
des trajets entre ces points
Ville4
Ville2
Ville6
Ville1
Ville5
Ville3
Quel débit d eau peut-on faire passer de la ville 1 à la ville 6 sans
faire déborder les canaux ?
 Flot  Maximal  
Problème : Dans un réseau possédant une source s et une sortie t, trouver
le débit maximum de la source vers la sortie.

Données de l algorithme:

n un graphe G=(V,E)

n un sommet source s
n un sommet cible t
n une capacité c: V x V à R

Trouver une relation de flot f: V x V à R telle que

n  f(u,v) ≤ c(u,v)
11 10
n  f(u,v) = -f(v,u)
7
n  ∑ f (u, w) = 0 20
w∈V
Sauf pour s et t 12
 Flot  Maximal  
Valeur du flot:

v( f ) = ∑ f ( s, y ) = ∑ f ( x, t )
y∈V x∈V

v(f) : quantité transportée par le réseau

1 1 10
11 7
7 3
8
s 10 s 10
3 t 3 t
15 15
8
12 8 8
2 2

Flot f
Graphe G
V(f)=25
 Flot  Maximal  

Soit G=(V,E) un graphe et f un flot

La capacité résiduelle d un arc (u,v) est

cf(u,v) = c(u,v) –f(u,v)

Le graphe résiduel de G est le graphe Gf=(V,Ef)

où:
{
E f = (u, v) ∈V ×V c f (u, v) > 0 }
Représente les arcs qui peuvent supporter un flot plus important
 Flot  Maximal  
Attention : les arcs du flot résiduels peuvent ne pas être des
arcs de G

Explication : f(u,v) >0 implique f(v,u) ≤ 0 et donc cf(v,u) = c(u,v) – f(v,u) >0
7
1 11
7 1
8 4
7
s 10 8
3 t
s 10
15 3 t
15
f(s,1)=f(1,t)=7

Interprétation : en envoyant 7 unités de t vers 1 (i.e annuler le flot)

puis envoyant
 Flot  Maximal  

Un chemin améliorant de G est un chemin p de s vers t sans cycle

La capacité du chemin est :

c f ( p) = min{c f (u, v) (u, v) ∈ p}

Idée : s il existe un chemin améliorant dans Gf, alors
le flot f peut être amélioré
 Flot  Maximal  

Algorithme (principe):
1 11
Répéter 7
8
trouver un chemin améliorant p
s 10
améliorer le flot f avec p 3 t
calculer le graphe résiduel Gf=(V,Ef) 15
Jusqu à flot stable 12 8
2

7
1 4
7
8
s 10
3 t
15
12 8
2
 Flot  Maximal  
Procedure Ford-Fulkerson(G,s,t)

Pour tout (u,v) dans A

f[u,v]:=0
f[v,u]:=0
finpour
Tant que ∃ un chemin p de s vers t dans Gf tel que
cf(u,v)>0 pout tout arc de p

trouver p chemin améliorant

cf(p) = min{ cf(u,v) | (u,v)∈ p }

pour tout (u,v)∈ p
f(u,v):= f(u,v)+ cf(p)
f(v,u):= -f(u,v)
finpour

fintantque
 Flot  Maximal  
7
1 11 1 4
7 7
8 8
s 10 s 10
3 t 3 t
15 15
12 8 12 8
2 2

7
7
1 4
7 1 4
8 7
10 8
s 10
3 t s
5 3 t
15
12 8 3
10 7 5
2 5 2
 Flot  Maximal  
7 7
1 4 1
7 4
8 7
8
s 10 10
3 t s
3 t
5 15 15
7 5
3 7
5 5 3
2 2

10
1
7 1
5
3
s V(f)= 25
3 t
10 15
4 8
12 2
 Flot  Maximal  

Le fait que de nouveau arcs apparaissent est gênant.

Si le choix du chemin améliorant est mal fait, l algorithme
peut ne pas terminer

Si les poids des arcs sont des entiers :

complexité en O( |E| . v(f*))

Avec f* le flot maximal trouvé par l algorithme

Une amélioration dans le choix du chemin (Edmonds-Karp)

permet de réduire la complexité à O( |V| . |E|2 )
 Flot  Maximal  
Procedure Edmonds-Karp(G,s,t)

Pour tout (u,v) dans A

f[u,v]:=0
f[v,u]:=0
finpour
Tant que ∃ un chemin p de s vers t dans Gf tel que
cf(u,v)>0 pout tout arc de p

trouver p de longueur minimale

/* parcours en largeur */
cf(p) = min{ cf(u,v) | (u,v)∈ p }
pour tout (u,v)∈ p
f(u,v):= f(u,v)+ cf(p)
f(v,u):= -f(u,v)
finpour

fintantque
 Connexité  
Un graphe non-orienté G=(V,E) est dit connexe s il existe un chemin de
tout sommet x à tout autre sommet y

Un graphe orienté G=(V,A) est dit connexe s il existe un chemin de tout sommet x
à tout autre sommet y dans le graphe G =(V,A∪A-1)

Un graphe orienté G=(V,A) est dit fortement connexe s il existe un chemin de

tout sommet x à tout autre sommet y dans G.
s2
s2 s0
s2 s0
s0

s3
s3 s1
s3 s1
s1
 Connexité  
Algorithme de Warshall

Procedure Warshall (C : tableau[1..n,1..n] de booléens,

A : tableau[1..n,1..n] de booléens
Var i,j,k: entiers

Pour i dans 1..n faire

Pour j dans 1..n faire
A[i,j] := C[i,j]
finpour
Pour k dans 1..n faire
Pour i dans 1..n faire
Pour j dans 1..n faire
A[i,j] := A[i,j] or (A[i,k] and A[k,j])
finpour
finpour
finpour
 Connexité  

Permet de construire la fermeture transitive d un graphe

C : graphe sous forme matricielle

A : fermeture transitive de C à la fin de l algorithme

si et sj dans la même composante connexe si A[i,j] = vrai

si et sj dans la même composante fortement connexe si

A[i,j] = vrai
et A[j,i] = vrai

Complexité en O(|V|3)
 Connexité  
Algorithme de Tiernan : detection de cycles élémentaires

Cycle : séquence de sommets qui

3 commence et finit sur le même sommet

4 Cycle élémentaire :
cycle qui ne passe pas deux fois
0   2 par un sommet (à l exception du sommet
de départ/fin du cycle)

[Link] , [Link] , [Link],

 Connexité  
Algorithme de Tiernan : detection de cycles élémentaires

Input : G, graph of size N

Initialisation

P:=0 ; H:= ∅N ;
/* H : tableau 1..N d ensemble d entiers
/* k ∈ H[i] if k has been considered as a successor of i */
k:=1
P[1]:=1 /* P = current path */

Find_Successor(G: graphe,P: tableau de sommets, k: entier,suc:sommet)

Var suc: entier
Suc:=-1
For j in 1,..,N do
If (1) j > P[1] /* j is not the origin of the cycle */
(2) j ∉ P /* j not in path */
(3) j ∉ H[P[k]] /* j not explored */
then suc := j; break
endfor
EC2 : Find_successor( G, P,k,j) /* path extension /

If this j > -1 /* extend the path */

K:=k+l;
P[k]:= j
go to EC2.
Else /* no j meets the conditions, the path cannot be extended */
EC3 [Circuit Confirmation]
If G[P[k],P[1]] = false then
no circuit has been formed, go to EC4.
Otherwise a circuit is reported, Print P.
EC4 [Vertex Closure]
If k = 1, then all of the circuits containing vertex P[1]
have been considered.
go to EC5.
Otherwise,
H[P[k]] := ∅
H[P[k - 1]]:= H[P[k - 1]] ∪ P[k]
P[k]:= 0
K:=k-1
go to EC2.
EC5: [Advance Initial Vertex]
If P[1] = N then, go to EC6 Otherwise,
P[1] := P[1] + 1 /* next vertecs as origin of cycles */
K := 1 ; H:= ∅N
go to EC2.
EC6: [Terminate]
 Connexité  

Algorithme de Tiernan

Calcule les cicuits elementaires

Utile pour obtenir une base de cycle : tout cycle de G est

ensuite une combinaison des cycles de cette base

Affichage unique de chaque circuit

Complexité :

For every vertex, a depth first search algorithm

O(n. (m+n))
 Composantes  connexes  
Algorithme de Tarjan

Permet de repérer les composantes connexes dans un graphe orienté

Principe :

Le graphe est parcouru en profondeur.

Un graphe orienté peut être séparé en deux groupes d arcs

ceux qui font partie de l exploration en profondeur →
ceux qui connectent les sommets à un de leurs
ancêtres : les « frondes » -à
Composantes  connexes  

9
7
4
8
6

0   3
10
5

2
Composantes  connexes  

9
7
4
8
6

0   3
10
5

2
Composantes  connexes  

9
7
4
8
6

0   3
10
5

2
 Composantes  connexes  

Soit G = (V,E) un graphe orienté

On définit la relation d équivalence suivante

v et w sont équivalents ssi
w apparait le long d un chemin allant de v à v (cycle)

On peut définir les sous-graphes

Gi=(Vi,Ei) comme les restrictions de G aux classes d équivalence
de V

On a:
n chaque Gi est fortement connexe
n chaque Gi est maximal
 Composantes  connexes  

Proposition : soient v,w deux sommet d une même composante connexe

et F une forêt couvrant G. Alors v et w ont un ancêtre
commun dans F

Proposition : Soit C une composante connexe de G, alors les sommets de C

définissent un sous-arbre d un arbre de F.

La racine de cet arbre est appelé racine de C

L algorithme de Tarjan consiste à repérer les racines

 Composantes  connexes  

On peut créer deux fonctions num(.) et numAccessible(.)

qui associent à tout sommet de G un numéro :

Num(v) = ordre d exploration dans le parcours

Numaccessible(v) = min { num(v)

∪ { num(w)| v(à)* -àw
& ∃ u, u(à)*v, u(à)*w
& u,w dans la même CC }

Propriété : les racines sont les sommets pour lesquels

num(v) = numaccessible(v)
 Composantes  connexes  
fonction tarjan(graphe G)
num := 0 /* numéro associé à chaque sommet dans le parcours */
P := pile vide
partition := ensemble vide

pour chaque sommet v de G

si [Link] n'est pas défini
parcours(G, v, P, partition)
finsi
renvoyer partition

fin de fonction
fonction parcours(G: graphe, num:entier, sommet v, P: pile , partition : liste)

[Link] := num
[Link] := num
num := num + 1
[Link](v)

pour chaque w successeur de v

si [Link] n'est pas défini /* w non exploré par la DFS */

parcours(G,num,w,P,partition)
[Link] := min([Link], [Link])

sinon si w ∈ P /* on vient de repérer un arc « fronde » */

[Link] := min([Link], [Link])
si [Link] = [Link]
/* C'est une racine, calcul de la CC détectée */
C := ∅
répéter
w := [Link]()
ajouter w à C
tant que w différent de v
ajouter C à partition
finsi
fin de fonction
Composantes  connexes  

10 11 12

10 11 12 10
10

13
13 11
 Composantes  connexes  

Résumé :

Recherche des composantes fortment connexes dans

un graphe orienté

Detection des racines lors du parcours en profondeur

Complexité en O( |V| + |E| )

 Conclusion  

Beaucoup de problèmes se modélisent comme des problèmes de graphes

problèmes de chemins optimaux

(itinéraire dans un réseau routier)

problèmes de cycles et de leurs poids

(saturation de réseaux)

Attention cependant :

tous les problèmes sur les graphes ne sont pas polynomiaux !

 Chemin  Hamiltonien  

Trouver un cycle dans un graphe qui passe exactement

une fois par chaque sommet

Application pratique :
tournée d un visiteur commercial, qui doit revenir
dans sa ville de départ après avoir visité des clients dans
chaque ville.

Problème NP-complet

si on choisit un cycle, on sait vérifier en temps polynomial

que c est un cycle, et qu il passe par tous les sommets.

Malheureusement, il n existe pas en général de stratégie

polynomiale pour construire un tel cycle
 Colora?on  de  graphe  

Associer une couleur à chaque sommet du graphe de manière

À ce que deux sommets consécutifs ne portent pas la même couleur

G=(V,E)

Trouver col: V  C telle que

∀(u,v) ∈ E, c(u) ≠ c(v)

Souvent assorti d une contrainte de minimalité :

|col (V)| = nombre chromatique

Problème NP-complet

On peut vérifier en temps linéaire en |E| qu une coloration

satisfait les conditions ci-dessus, mais on risque d avoir à considérer
toutes les colorations possibles
 Bibliographie  
[1] Christine Froidevaux, Marie-Claude Gaudel, Michèle Soria,
Types de Données et Algorithmes, McGraw-Hill, 1990.

[2] Thomas Cormen, Charles Leiserson, Ronald Rivest,

Introduction à l algorithmique, Dunod, 1994.

[3] Michel Gondran, Michel Minoux,

Graphes et algorithmes, Eyrolles, 1985