IUT Info 2 GI F.

Madelaine
Année 2007-08 Cours sur les graphes : les algorithmes C. Simon
Période 1 et 2

1 L’algorithme de Bellman-Ford et ses variantes

Dans le cas classique, il s’agit de calculer les distances des plus courts che- Algorithme 1 : Bellman-Ford
mins depuis une source s à chaque autre sommet v d’un graphe orienté valué Données
→
− →
−
G . Les distances sont non pas en termes de nombres d’arcs d’un chemin mais, G un graphe orienté valué sans circuit de longueur strictement négative
en termes de somme des valeurs de chaque arc qui le compose. En effet, on →
−
s un sommet de G
travaille sur un graphe orienté valué, c’est-à-dire qu’on dispose d’une fonction Variables locales
→
−
sur les arcs de G à valeur dans R. En termes plus informatique, on a à notre L tableau des distances depuis s /* indexé par les sommets */
disposition la fonction suivante : (u, v) un arc
début
initialisation
L[s] := 0
pour tous les sommet v 6= s faire L[v] := +∞
tant que L change faire
/* relaxation de l’arc (u, v) */
→
−
→
− pour chaque arc (u, v) de G faire
– length(u, v, G ) : renvoie la valeur de l’arc (u, v) dans le graphe orienté →
−
→
− si L(v)>L(u)+length((u, v, G )) alors
valué G (si l’arc existe). →
−
L(v) :=L(u)+length((u, v, G ))
finsi
finprch
fintq
fin
Sorties : L, le tableau des distances des plus court chemins de s

Ici, nous détaillons l’algorithme dans le cas où l’entrée a un plus court che-
min. Autrement dit, si le graphe n’a pas de circuit de longueur strictement
négative.

1
Les Algorithmes Cours sur les graphes

Mémoriser les chemins. Algorithme 2 : Bellman-Ford (amélioré)

Données
En plus de calculer la longueur d’un plus court chemin depuis s, on peut →
−
G un graphe orienté valué connexe
aussi stocker un plus court chemin. En effet, à chaque fois qu’on relâche un arc →
−
s un sommet de G
(u, v), cela signifie que le chemin de s à v passe dorénavant par u, autrement dit
Variables locales
le prédécesseur de v est maintenant le sommet u. On peut par exemple stocker
L tableau des distances depuis s
ces prédécesseurs dans un tableaux indexé par les sommets du graphe. Voir
P red tableau des prédécesseurs sur un plus court chemin depuis s
l’algorithme 2 ci-contre pour une implémentation (les lignes correspondantes
Circuit? Booléen vrai ssi il y a un circuit négatif
sont en bleu).
(u, v) un arc
début
initialisation
Détecter si un graphe quelconque a un circuit négatif. L[s] := 0
pour tous les sommet v 6= s faire L[v] := +∞
On peut montrer que l’algorithme de Bellman-Ford (Algorithme 1) s’arrête Circuit? := faux.
après au plus n − 1 executions de la boucle Tant que, dans le cas d’un graphe pour x = 0 à n − 1 faire
→
−
sans circuit de poids négatif (ici n est le nombres de sommets du graphe). pour chaque arc (u, v) de G faire
→
−
La preuve se fait par récurrence sur le nombre d’itérations et l’hypothèse de si L(v)>L(u)+length((u, v, G )) alors
récurrence est la suivante. Au bout de x itérations de la boucle Tant Que, →
−
L(v) :=L(u)+length((u, v, G ))
pour tout sommet v, L[v] est la longueur du plus court chemin de s à v parmi Pred[v] :=u
ceux qui ont au plus x arcs. finsi
finprch
Si un graphe connexe a un circuit négatif, alors il n’y a pas de plus court finpour
chemin depuis s vers certains sommets (en particuliers ceux qui sont sur ce →
−
pour chaque arc (u, v) de G faire
circuit négatif). Donc, l’algorithme 1 sur un tel graphe executerait indéfini- →
−
si L(v)>L(u)+length((u, v, G )) alors
ment dans la boucle Tant Que. En particulier, cette dernière s’executerait au Circuit? := vrai
moins n fois. On peut donc executer la boucle Tant Que n fois sur un graphe finsi
quelconque, et si à la dernière itération, la valeur de L change, alors on sait
finprch
qu’il y a un circuit négatif.
fin
Voir l’algorithme 2 ci-contre pour une implémentation (les lignes corres- Sorties : L, P red, Circuit?.
pondantes sont en vert).

2
Les Algorithmes Cours sur les graphes

Variantes Plus long chemin vers un sommet Au lieu de calculer des plus courts
chemins depuis s vers tous les sommets, on peut calculer la distance des plus
Le cas dual : distance vers un sommet Au lieu de calculer des plus
longs chemins. Bien evidemment, l’algorithme a maintenant des limitations
courts chemins depuis s vers tous les sommets, on peut calculer la distance
différentes : il n’a de sens que dans un graphe sans circuit strictement positif
des plus courts chemins depuis n’importe quel sommet à un sommet t (voir
(voir algorithme 4).
algorithme 3).

Algorithme 3 : Variante de Bellman-Ford (le cas dual) Algorithme 4 : Autre variante de Bellman-Ford (plus long chemin)
Données Données
→
− →
−
G un graphe orienté valué sans circuit de longueur strictement négative G un graphe orienté valué sans circuit de longueur strictement positive
→
− →
−
t un sommet de G s un sommet de G
Variables locales Variables locales
L tableau des distances vers un sommet à t L tableau des distances depuis un sommet s
Succ tableau des successeurs sur un plus court chemin à t P red tableau des successeurs sur un plus court chemin à t
(u, v) un arc (u, v) un arc
début début
initialisation initialisation
L[t] := 0 L[s] := 0
pour tous les sommet v 6= t faire L[v] := +∞ pour tous les sommet v 6= s faire L[v] := −∞
tant que L change faire tant que L change faire
→
− →
−
pour chaque arc (u, v) de G faire pour chaque arc (u, v) de G faire
−
→ →
−
si L(u)>L(v)+length((u, v, G )) alors si L(v)<L(u)+length((u, v, G )) alors
→
− →
−
L(u) :=L(v)+length((u, v, G )) L(v) :=L(u)+length((u, v, G ))
Succ[u] :=v Pred[v] :=u
finsi finsi
finprch finprch
fintq fintq
fin fin
Sorties : L, succ Sorties : L, Pred

3
Les Algorithmes Cours sur les graphes

2 Parcours
Dans un graphe non-orienté G à partir d’un sommet s, on découvre les – popFront(P ) : enlève le premier sommet de la pile P (si celle-ci n’est pas
sommets de la composante connexe de s dans G (c’est-à-dire l’ensemble des vide).
sommets accessibles par un chemin depuis s dans G). Lors du calcul, on utilise
un ensemble Z pour stocker les sommets déjà visités, et une variable F pour
stocker les sommets de la frontière, c’est-à-dire ceux ayant au moins un voisin
non visité. Selon la structure de donnée qu’on utilise pour F on obtient des Algorithmes de parcours
parcours différents.
Algorithme 5 : Parcours général
Structures de données Données
G un graphe
L’ensemble
s un sommet de G
On dispose des fonctions suivantes sur un ensemble S. Variables locales
– choose(S) : renvoie un sommet x de S (si S n’est pas vide). Z un ensemble /* zone connue */
– empty?(S) : renvoie vrai ssi S est l’ensemble vide. F un ensemble /* la frontière */
– add(x, S) : ajoute x à l’ensemble S.
u, v deux sommets
– remove(x, S) : enlève x de l’ensemble S (si x appartient à S).
début
initialisation
La file add(s,Z)
On dispose des fonctions suivantes sur une file Q. add(s,F )
– checkFront(Q) : renvoie le premier sommet de F (si Q n’est pas vide). répéter
– empty?(Q) : renvoie vrai ssi Q est la file vide. v :=choose (F )
– pushBack(x, Q) : ajoute x à l’arrière de la file Q. si il existe u 6∈ Z adjacent à v alors
– popFront(Q) : enlève le premier sommet de la file Q (si celle-ci n’est pas add(u,F ) /* première visite de u */
vide). add(u,Z)
sinon
La pile remove(v,F ) /* dernière visite de v */
On dispose des fonctions suivantes sur une pile P . finsi
– checkFront(P ) : renvoie le premier sommet de P (si P n’est pas vide). jusqu’à empty ?(F )
– empty?(P ) : renvoie vrai ssi P est la pile vide. fin
– pushFront(x, P ) : ajoute x au début de la pile P .

4
Les Algorithmes Cours sur les graphes

Algorithme 6 : Parcours en largeur Algorithme 7 : Parcours en profondeur

Données Données
G un graphe G un graphe
s un sommet de G s un sommet de G
Variables locales Variables locales
Z un ensemble /* zone connue */ Z un ensemble /* zone connue */
F une file /* la frontière */ F une pile /* la frontière */
u, v deux sommets u, v deux sommets
début début
initialisation initialisation
add(s,Z) add(s,Z)
pushBack(s,F ) pushFront(s,F )
répéter répéter
v :=checkFront (F ) v :=checkFront (F )
si il existe u 6∈ Z adjacent à v alors si il existe u 6∈ Z adjacent à v alors
add(u,Z) /* première visite de u */ add(u,Z) /* première visite de u */
pushBack(u,F ) pushFront(u,F )
sinon sinon
popFront(F ) /* dernière visite de v */ popFront(F ) /* dernière visite de v */
finsi finsi
jusqu’à empty ?(F ) jusqu’à empty ?(F )
fin fin

5
Les Algorithmes Cours sur les graphes

Application du parcours en largeur Applications du parcours en profondeur

On s’intéresse au moment où on visite un sommet pour la première
Distance à la source On peut calculer la distance depuis la source s à fois et celui où on le visite pour la dernière fois. On a deux tableaux
chaque sommet v du graphe (si G est connexe). En effet, on peut facilement Début et Fin dans lesquels on stocke les temps correspondant. On me-
observer que les niveaux de l’arbre (= distance à la racine) correspondent à la sure le temps en termes du nombre x d’executions de la boucle répéter.
distance à la source. Algorithme 9 : Parcours en profondeur + début et fin
Données
Algorithme 8 : Parcours en largeur + distance à la source
G un graphe connexe et s un sommet de G
Données
Variables locales
G un graphe connexe et s un sommet de G
Z un ensemble, F une pile et u, v deux sommets
Variables locales
Debut et Fin deux tableaux /* indexés par les sommets */
Z un ensemble, F une file, u, v deux sommets
début
L tableau des distances à la source /* indexés par les sommets */ initialisation
début x=0
initialisation
add(s,Z)
add(s,Z)
pushFront(s,F )
pushBack(s,F )
Début[s] := x
L[s] := 0
répéter
répéter x := x + 1
v :=checkFront (F ) v :=checkFront (F )
si il existe u 6∈ Z adjacent à v alors si il existe u 6∈ Z adjacent à v alors
add(u,Z) /* première visite de u */ add(u,Z) /* première visite de u */
pushBack(u,F ) pushFront(u,F )
L[u] := L[v] + 1 Début[s] := x
sinon sinon
popFront(F ) /* dernière visite de v */ popFront(F ) /* dernière visite de v */
finsi Fin[s] := x
jusqu’à empty ?(F ) finsi
fin jusqu’à empty ?(F )
Sorties : L, tableau des distances à la source s fin

6
Les Algorithmes Cours sur les graphes

Algorithme 10 : Parcours en profondeur + Tri Topologique

Données
→
−
G un graphe orienté sans cycle
s un sommet de G
Variables locales
Z un ensemble, F une pile et u, v deux sommets
Priorité un tableau /* indexé par les sommets */
début
initialisation
x=0
add(s,Z)
pushFront(s,F )
Le Tri topologique. On dispose d’un graphe orienté sans cycle. Un tel répéter
graphe représente typiquement un problème d’ordonnancement de tâches : un x := x + 1
sommet correspond à une tâche et un arc (u, v) indique la contrainte de précé- v :=checkFront (F )
dence “la tâche u doit être terminée avant que la tâche v ne puisse commencer ”. si il existe u 6∈ Z successeur de v alors
Le problème du tri topologique consiste à ordonner les sommets du graphe de add(u,Z) /* première visite de u */
telle sorte que si il y a un arc (u, v) alors u vient avant v dans l’ordre calculé. pushFront(u,F )
sinon
popFront(F ) /* dernière visite de v */
Bien que le graphe soit orienté, on peut parfaitement y appliquer l’algo- Priorité[s] := x
rithme de parcours en profondeur. On peut observer que la dernière visite d’un finsi
sommet a forcément lieu avant la dernière visite d’un sommet qui le précède. jusqu’à empty ?(F )
Ainsi, on peut voir les valeurs calculées dans le tableau Fin comme des valeurs
fin
de priorité : plus la valeur est haute, plus la tâche est importante. Autrement
Sorties : Priorité
dit, l’ordre inverse de celui donné par Fin est un ordre topologique.