Arbres et arborescences

Algorithme de KRUSKAL

 Permet la recherche d’un arbre de poids minimal

 Principe:
1. Numéroter les arcs par ordre des poids croissant, en suite construire
progressivement l’arbre en ajoutant les arcs un par un
2. Un arc n’est ajouté que s’il ne construit pas un cycle, si non en passe à l’arc
suivant dans l’ordre de la liste
3. On s’arrête lorsque le nombre d’arcs ajouté est égale au nombre de sommets
moins un
Application

 Soit le graphe suivant:

2 1
1 2 3

3
2 2
1

1
4 5
Application

 initialisation:
 W=∅ , n=5, k=0

N° 1 2 3 4 5 6 7
arrête (2, 3) (3,5) (4,5) (3,4) (2,5) (1,2) (1,3)
poids 1 1 1 2 2 2 3

Itération 1
(2, 3) ne construit pas un cycle
w=((2, 3)), K=k+1=1 <5-1
Application

 Itération 2
(3, 5) ne construit pas un cycle
w=((2, 3), (3,5)), K=k+1=2 <5-1
 Itération 3
(4, 5) ne construit pas un cycle
w=((2, 3), (3,5), (4, 5)), K=k+1=3 <5-1
 Itération 4
(4, 3) construit un cycle alors dépasser
Application

 Itération 5
(2, 5) construit un cycle alors dépasser
 Itération 6
(1, 2) ne construit pas un cycle
w=((2, 3), (3,5), (4, 5), (1, 2) ), K=k+1=4 =5-1 Fin
P(w)=5
Application

 L’arbre du poids minimal est donc:

1 2 3

4 5

 P(A)=5
 Algorithme de PRIM
 Permet la recherche d’un arbre de poids minimale
 Démarche:
1. Choisir un sommet x du graphe
2. Examiner les arrêtes voisines à x
3. Sélectionner celle ayant le plus petit poids
4. Examiner les arrêtes voisines à l’arrête sélectionnée précédemment
5. Sélectionner celle ayant le plus petits poids
6. Une arrête n’est sélectionnée que si elles ne construit pas un cycle
7. Répéter le même processus jusqu’à ce que le nombre des arrêtes sélectionnées, m,
est égale au nombre de sommets, n , moins un (m = n-1).
 Application:

 Reprenant le graphe de l’exemple précédant

Initialisation 2 1
1 2 3
W=∅ , n=5, k=0
3
Itération 1:
2 2
Choisir un sommet de G, soit ‘5’
1
Min(d(5,2),d(5,3),d(5,4))=min(2,1,1)=1
Donc (5,3)ou (5,4), on prend (5,3) 1
4 5
K=k+1=1 <5-1 , w=((5,3))
Itération 2:
Min(d(3,2),d(3,1),d(3,4), d(5,4), d(5,2))=min(1,3,2,1,2)=1
Donc (3,2)ou (5,4), on prend (5,4)
K=k+1=2 <5-1 , w=((5,3), (5,4))
 Application:
Itération 3:
Min(d(3,2),d(3,1), d(5,2))=min(1,3,2)=1
2 1
Donc (3,2) 1 2 3
K=k+1=3 <5-1 , w=((5,3), (5,4), (3,2))
Itération 4:
Min(d(2,1),d(3,1))=min(2,3)=2 1
Donc (2,1)
1
K=k+1=4 =5-1 , w=((5,3), (5,4), (3,2), (2,1)) Fin. 4 5
P(A)=5
 Problème de recherche d’un plus
court chemin
 Le graphe suivant représente les routes à sens unique reliant deux points A et E

2
B
2 6 D
2
A 3 E
1 7
C

 Il existe plusieurs chemins reliant A à E, mais on veut trouver celui de distance minimale
 On remarque que le plus court chemin de A à E est (ABDE), il a pour langueur 6.
 Problème de recherche d’un plus
court chemin
 Le principe de la recherche d’un plus court chemin entre deux sommets est de trouver
tous les chemins les reliant et d’en choisir le plus court.
 Définitions:
1. Réseau:
c’est un graphe muni d’une application d:U՜ 𝑅 qui à chaque arc fait correspondre sa
longueur d(U)
un réseau est noté par : R=(X,U,d)
pratiquement d(U) peut être un coût, une distance, une durée,…
Problème de recherche d’un plus
court chemin
2. Longueur d’un chemin dans un réseau:
C’est la somme des longueurs des arcs
3. Plus courte distance:
C’est la longueur du plus court chemin, noté 𝝅(𝒙) tel que x est l’éxtrémité
términale du plus court chemin.
 Problème de recherche d’un plus
court chemin
Exemple:
1 4 -1
Le plus court chemin de A à B est C=(A,B) sa longueur A B D E

Est 1, donc 𝝅(𝑩) =1 est la plus courte distance 2 -3

2 3
C F

4. Circuit absorbant:
C’est un circuit de longueur négatif.
exemple:
Le circuit (DEFD) est absorbant.
Algorithme de recherche d’un plus
court chemin
a) Algorithme de BELLMAN:
On applique cet algorithme pour la recherche d’une arborescence des plus
court chemins dans un réseau R(X,U,d) sans circuit.
Le principe :
 L'idée de cet algorithme est de calculer de proche en proche
l'arborescence des plus courtes distances, issues du sommet s à un sommet
donné y.
 On ne calcule la plus courte distance de s à y, que si on à déjà calculer les
plus courtes distances de s à tous les prédécesseurs de y.
 Algorithme de BELLMAN
Données : un réseau R=(X,U,d) sans circuit
Résultats : arborescence de plus courtes distances A.
0- Initialisation :
Soit s un sommet de X, on pose S={s} et 𝜋 𝑠 = 0, 𝐴 = ∅
1- Chercher un sommet dans tous les prédécesseurs sont dans S.
Si un tel sommet n'existe pas; terminer
Dans ce cas soit S=X, ou le sommet s n'est pas une racine dans R.
Si un tel sommet existe; Aller à (2)

2- On pose 𝜋 𝑥 = min 𝜋 𝐼 𝑢 +𝑑 𝑢

Soit u' l'arc pour lequel 𝜋 𝑥 = 𝜋(𝑙 𝑢′ ) + 𝑑(𝑢′ )

A=A ∪ 𝑢′ ; S=S ∪ 𝑥 Aller à (1)
 Algorithme de BELLMAN
2
Application: Soit les réseau suivant B
2 6 D
0- initialisation 2
A 3
S= 𝐴 , 𝝅(𝑨) =0, 𝑨 =∅ 1
C 7 E
Itération 1
B∈
ഥ S et tous ses prédecesseurs sont dans S alors
𝝅(𝑩) = 𝝅(𝑨) +d(AB)=0+2=2 ֜ 𝝅(𝑩) = 2
S=S∪ 𝑩 = 𝐴, 𝐵 , 𝑨 = 𝑨 ∪ 𝑨𝑩 = 𝑨𝑩
Itération 2:
Les sommets D,C ∈
ഥ S , et tous leur prédecesseurs sont dans S alors
𝝅(𝑫) = 𝐦𝐢𝐧(𝝅(𝑩) +d(BD), 𝝅(𝑨) +d(AD)) =min(2+2, 0+6)=4 ֜ 𝝅(𝑫) = 4
𝝅(𝑪) = 𝐦𝐢𝐧(𝝅(𝑩) +d(BC), 𝝅(𝑨) +d(AC)) =min(2+3, 0+1)=1 ֜ 𝝅(𝑪) = 1
S=S∪ 𝑩 = 𝐷, 𝐶 = 𝐴, 𝐵, 𝐷, 𝐶 , 𝑨 = 𝑨 ∪ 𝑩𝑫, 𝑨𝑪 = 𝑨𝑩, 𝑩𝑫, 𝑨𝑪
 Algorithme de BELLMAN

Itération 3
E∈
ഥ S et tous ses prédecesseurs sont dans S alors
𝝅(𝑬) = 𝐦𝐢𝐧(𝝅(𝑫) +d(DE), 𝝅(𝑪) +d(CE)) =min(4 +2, 1+7)=6 ֜ 𝝅(𝑬) = 6

S=S∪ 𝑬 = 𝐴, 𝐵, 𝐷, 𝐶, 𝐸 =X, 𝑨 = 𝑨 ∪ 𝑫𝑬 = 𝑨𝑩, 𝑩𝑫, 𝑨𝑪, 𝑫𝑬

On a S=X alors fin, donc l’arborescence des plus courtes distance est:
2 2
B
2 D
2
A
1
C E
Algorithme de recherche d’un plus
court chemin
b) Algorithme de DIJKSTRA
On applique cet algorithme pour déterminer une arborescence des plus
courtes distances sur un réseau R=(X,U ,d), où les longueurs des arcs sont
positives ou nulles.
Le principe :
L’idée de cet algorithme est de calculer de proche en proche
l’arborescence des plus courtes distances issues du sommet s à un sommet
donné p.
Algorithme de recherche d’un plus court chemin
Algorithme de DIJKSTRA
 Enoncé :
Données: un réseau R=(X,U,d) avec d(u)≥ 0, ∀ 𝑢 ∈ 𝑈
Résultats: arborescence de plus courtes distances A.
0- Initialisation:
Soit s un sommet de X.
On pose S={s},𝜋 𝑠 = 0, 𝜋 𝑥 = ∞ ∀𝑥 ∈ 𝑋 − 𝑠 , 𝐴 = ∅, 𝛼 = 𝑠.
(𝛼 𝑒𝑠𝑡 𝑙𝑒 𝑑𝑒𝑟𝑛𝑖𝑒𝑟 𝑠𝑜𝑚𝑚𝑒𝑡 𝑖𝑛𝑡𝑟𝑜𝑑𝑢𝑖𝑡 𝑑𝑎𝑛𝑠 𝑆)
1- Examiner tous les arcs dont l’extrémité initiale est 𝛼 (I(u)= 𝛼), et l’extrémité terminale
n’appartient pas à S (T(u)=y / y∈ഥ 𝑆 ).
Si 𝜋 𝛼 + 𝑑 𝑢 < 𝜋 𝑦 , on pose 𝜋 𝑦 = 𝜋 𝛼 + 𝑑 𝑢 et 𝐴 = 𝑢, allez en (2).
2- Choisir un sommet z ∈ S tel que 𝜋 𝑧 = min{𝜋 𝑦 /y ∈
ഥ 𝑆}
➢ Si 𝜋 𝑧 = ∞ alors Terminer. Le sommet s n’est pas une racine.
➢ Si 𝜋 𝑧 < ∞ alors on pose 𝛼 = 𝑧, et 𝑆 = 𝑆 ∪ {𝛼}
➢ Si S=X ; alors terminer. A est l’arborescence des plus courts chenins issue de s.
➢ Si S≠ 𝑋 allez en (1).
 Algorithme de recherche d’un plus court chemin
Algorithme de DIJKSTRA

 Application:
Initialisation:
S={a},𝜋 𝑎 = 0, 𝐴 = ∅, 𝛼 = 𝑎
2
b
X a b c d e 2 e
𝜋 𝑥 0 ∞ ∞ ∞ ∞ 1 7
a 3
Itération 1
6 c d
Examiner les arcs ab, ac : b, c ∈
ഥS
2
𝜋 𝑎 + 𝑑 𝑎𝑏 = 0 + 2 = 2 < 𝜋 𝑏 =∞ alors 𝜋 𝑏 = 2
𝜋 𝑎 + 𝑑 𝑎𝑐 = 0 + 6 = 6 < 𝜋 𝑐 =∞ alors 𝜋 𝑐 = 6
X a b c d e
𝜋 𝑥 0 2 6 ∞ ∞
𝜋 𝑧 = 𝑚𝑖𝑛(𝜋 𝑦 /𝑦 ∈ 𝑆)=min(𝜋 𝑏 , 𝜋 𝑐 , 𝜋 𝑑 , 𝜋 𝑒 )=min(2, 6, ∞, ∞)=2
Z=b, on pose 𝛼 = 𝑏, S={a, b}≠X, A ={(a b)}
 Algorithme de recherche d’un plus court chemin
Algorithme de DIJKSTRA

 Itération 2:
Examiner l’arc be:e∈
ഥS
𝜋 𝑏 + 𝑑 𝑏𝑒 = 2 + 2 = 4 < 𝜋 𝑒 =∞ alors 𝜋 𝑒 = 4
X a b c d e
𝜋 𝑥 0 2 6 ∞ 4
𝜋 𝑧 = 𝑚𝑖𝑛(𝜋 𝑦 /𝑦 ∈ 𝑆)=min(𝜋 𝑐 , 𝜋 𝑑 , 𝜋 𝑒 )=min(6, ∞, 4)=4
Z=e, on pose 𝛼 = 𝑒, S={a, b, e}≠X, A ={(a b), (be)}
 Algorithme de recherche d’un plus court chemin
Algorithme de DIJKSTRA
 Itération 3:
Examiner les arcs ec, ed:c, d ∈
ഥS
𝜋 𝑒 + 𝑑 𝑒𝑐 = 4 + 1 = 5 < 𝜋 𝑐 =6 alors 𝜋 𝑐 = 5
𝜋 𝑒 + 𝑑 𝑒𝑑 = 4 + 7 = 11 < 𝜋 𝑑 =∞ alors 𝜋 𝑑 = 11
X a b c d e
𝜋 𝑥 0 2 5 11 4
𝜋 𝑧 = 𝑚𝑖𝑛(𝜋 𝑦 /𝑦 ∈ 𝑆)=min(𝜋 𝑐 , 𝜋 𝑑 )=min(5, 11)=5
Z=c, on pose 𝛼 = 𝑐, S={a, b, e,c}≠X, A ={(a b), (be), 𝑒𝑐 }
Algorithme de recherche d’un plus court chemin
Algorithme de DIJKSTRA

 Itération 4:
Examiner l’arcs (cd):d ∈
ഥS
𝜋 𝑐 + 𝑑 𝑐𝑑 = 5 + 2 = 7 < 𝜋 𝑑 =11 alors 𝜋 𝑑 = 7
X a b c d e
𝜋 𝑥 0 2 5 7 4
𝜋 𝑧 = 𝑚𝑖𝑛(𝜋 𝑦 /𝑦 ∈ 𝑆)=min(𝜋 𝑑 )=min(7)=7
Z=d, on pose 𝛼 = 𝑑, S={a, b, e,c,d}=X, A ={(a b), (be), 𝑒𝑐 ,(cd)}. FIN

2
b
2 e
1
a

c d
2
Algorithme de recherche d’un plus court chemin
Algorithme général de FORD

 Algorithme général de FORD:

 On applique cet algorithme pour la recherche d'une arborescence de plus
courts chemins dans un réseau quelconque avec d(u) ∈ 𝑅.
 Cet algorithme permet soit :
 De mettre en évidence un circuit absorbant si celui-ci existe.
 De déterminer une arborescence de plus courts chemins dans un réseau.
 Le principe:
 Consiste à améliorer une arborescence réalisable (initiale) (X,A) de racine s
jusqu'à l’obtention d’une arborescence optimale de plus courts chemins,
issue de s.
Algorithme de recherche d’un plus court chemin
Algorithme général de FORD
 Enoncé :
 Données: un réseau R=(X,U,d) avec d(u) ∈ 𝑅
 Résultats: arborescence de plus courtes distances A.
0-Initialisation:
 Soit (X,A) une arborescence de racine s dans le réseau R et 𝜋(𝑥) les longueurs des
chemins de s à x dans l’arborescence (X,A).
1- Chercher un arc 𝑢 = (𝑖, 𝑗) dans le réseau R, n’appartenant pas à A , tel que :
 𝛿 𝑢 = 𝜋 𝑗 − 𝜋 𝑖 − 𝑑(𝑖, 𝑗) > 0
 Si un tel arc n’existe pas , terminer, (X,A) est optimal.
 Si un tel arc existe, aller à (2)
2- Tester si (X,A∪ 𝑢 ) contient un circuit.
 Si oui ; examiner s’il est absorbant (s’il l’est, terminer, le problème n’admet pas de
solution)
 Sinon aller à (3)
3- Chercher un arc v ∈ 𝐴 tel que T(v)=j=T(u)
 On pose : A= A∪ 𝑢 / 𝑣
 Soit X’= 𝑗 ∪ 𝑑𝑒𝑠𝑐𝑒𝑛𝑑𝑎𝑛𝑡 𝑑𝑒 𝑗 𝑑𝑎𝑛𝑠 𝑙′ 𝑎𝑟𝑏𝑜𝑟𝑒𝑠𝑐𝑒𝑛𝑐𝑒 𝐴
 On pose : 𝜋 𝑦 = 𝜋 𝑦 − 𝛿 𝑢 ∀ 𝑦 ∈ 𝑋′, aller à (1).
Algorithme de recherche d’un plus court chemin
Algorithme général de FORD

 Application
Soit le réseau suivant

2
2 5
2
3 2 2

1 -3 4 3 7
0 2
2 6
3 6
1
Algorithme de recherche d’un plus court chemin
Algorithme général de FORD
 Application
Initialisation: soit A=(1,2),(1,3),(3,6),(6,4),(2,5),(5,7) une arborescence initiale
Itération 1:
Les arcs n’appartenant pas à A sont : (2,3 ),(2,4),(4,3),(4,5),(6,5)(6,7)
𝛿 2,3 =𝜋 3 −𝜋 2 −𝑑 2,3 = 2>0
𝛿 2,4 =𝜋 4 −𝜋 2 −𝑑 2,4 =0
𝛿 4,3 =𝜋 3 −𝜋 4 −𝑑 4,3 = −3
𝛿 4,5 =𝜋 5 −𝜋 4 −𝑑 4,5 = −2
𝛿 6,5 =𝜋 5 −𝜋 6 −𝑑 6,5 = −1
𝛿 6,7 =𝜋 7 −𝜋 6 −𝑑 6,7 = −2
L’arc 2,3 n’est pas dans A, A∪ 2,3 ne contient pas de circuit, donc:
T 2,3 =T 1,3 =3 alors 1,3 sort de A et 2,3 entre dans A.
X’=3 ∪ les descendants de 3 dans A
X’={3,4,6}
On pose:
𝜋 3 =𝜋 3 -𝛿 2,3 =0
𝜋 6 =𝜋 6 -𝛿 2,3 =1
𝜋 4 =𝜋 4 -𝛿 2,3 =3
Algorithme de recherche d’un plus court chemin
Algorithme général de FORD

 La nouvelle arborescence est donc:

2
2 5
2
3 2 2

1 -3 4 3 7
0 2
2 6
3 6
1
Algorithme de recherche d’un plus court chemin
Algorithme général de FORD
 Itération 2:
Les arcs n’appartenant pas à A sont : (1,3 ),(2,4),(4,3),(4,5),(6,5)(6,7)
𝛿 1,3 = 𝜋 3 − 𝜋 1 − 𝑑 1,3 = −2
𝛿 2,4 = 𝜋 4 − 𝜋 2 − 𝑑 2,4 = −2
𝛿 4,3 = 𝜋 3 − 𝜋 4 − 𝑑 4,3 = −3
𝛿 4,5 = 𝜋 5 − 𝜋 4 − 𝑑 4,5 = 0
𝛿 6,5 = 𝜋 5 − 𝜋 6 − 𝑑 6,5 = 1>0
𝛿 6,7 = 𝜋 7 − 𝜋 6 − 𝑑 6,7 = 0
L’arc 6,5 n’est pas dans A, A∪ 6,5 ne contient pas de circuit, donc:
T 2,5 =T 6,5 =5 alors 2,5 sort de A et 6,5 entre dans A.
X’=5 ∪ les descendants de 5 dans A
X’={5,7}
On pose:
𝜋 5 =𝜋 5 -𝛿 6,5 =4
𝜋 7 =𝜋 7 -𝛿 6,5 =6
Algorithme de recherche d’un plus court chemin
Algorithme général de FORD

 La nouvelle arborescence est donc:

2
2 5
2
3 2 2

1 -3 4 3 7
0 2
2 6
3 6
1
Algorithme de recherche d’un plus court chemin
Algorithme général de FORD

 Itération 3:
Les arcs n’appartenant pas à A sont : (1,3 ),(2,4),(4,3),(4,5),(2,5)(6,7)
𝛿 1,3 = 𝜋 3 − 𝜋 1 − 𝑑 1,3 = −2
𝛿 2,4 = 𝜋 4 − 𝜋 2 − 𝑑 2,4 = −1
𝛿 4,3 = 𝜋 3 − 𝜋 4 − 𝑑 4,3 = −2
𝛿 4,5 = 𝜋 5 − 𝜋 4 − 𝑑 4,5 =-3
𝛿 2,5 = 𝜋 5 − 𝜋 6 − 𝑑 6,5 = −1
𝛿 6,7 = 𝜋 7 − 𝜋 6 − 𝑑 6,7 = −1
Il n’existe pas un arc u tel que 𝛿 𝑢 >0 alors l’arborescence est optimal.
Algorithme de recherche d’un plus court chemin
Algorithme général de FORD

2 5
2
3

1 -3 4 3 7
2
3 6
1