Scribd
Importer
63 vues11 pages

1 Application de L'algorithme de Floyd-Warshall: Institut Galilée - L3 Informatique - 2024 Algorithmique de Graphes: PCC

Le document traite de l'application des algorithmes de Floyd-Warshall, Ford et Ford-Bellman pour déterminer les plus courts chemins dans des graphes. Il explore également la complexité exponentielle de l'algorithme de Ford et présente des exercices sur la transformation de graphes et le calcul de circuits de longueur minimale. Enfin, il propose des questions sur l'application de ces algorithmes dans divers scénarios de graphes.

Transféré par

kacin126
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd
63 vues11 pages

1 Application de L'algorithme de Floyd-Warshall: Institut Galilée - L3 Informatique - 2024 Algorithmique de Graphes: PCC

Le document traite de l'application des algorithmes de Floyd-Warshall, Ford et Ford-Bellman pour déterminer les plus courts chemins dans des graphes. Il explore également la complexité exponentielle de l'algorithme de Ford et présente des exercices sur la transformation de graphes et le calcul de circuits de longueur minimale. Enfin, il propose des questions sur l'application de ces algorithmes dans divers scénarios de graphes.

Transféré par

kacin126
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

Institut Galilée – L3 Informatique – 2024 Algorithmique de graphes : PCC

1 Application de l’algorithme de Floyd-Warshall

1. Appliquer l’algorithme de Floyd-Warshall au graphe ci-dessus.


2. Tracer l’arborescence des plus courts chemins issus du sommet 3 obtenue.

2 Algorithmes de Ford, Ford-Bellman


2.1 Complexité exponentielle de l’algorithme de Ford
Le but de cet exercice est de montrer que le nombre d’itérations effectuées par l’algorithme de Ford peut
être exponentiel.
On considère la famille de graphes valués G(n), n ≥ 0 définie de la manière suivante :
— Le graphe G(0) est constitué de l’unique sommet a0 .
— Le graphe G(n), n ≥ 1 est obtenu à partir de G(n − 1) en ajoutant deux sommets an et bn et les arcs
(an , an−1 ) et (bn , an−1 ) de valuation van an−1 = vbn an−1 = 0 et l’arc (an , bn ) de valuation van bn = 3n .
1. Tracer le graphe G(3).
2. Soit S(n) la suite d’arcs de G(n), n ≥ 1 défini par la récurrence suivante :
— S(1) = ((a1 b1 ), (b1 a0 ), (a1 a0 ))
— S(n) = ((an bn ), (bn an−1 ), S(n − 1), (an an−1 ), S(n − 1)) pour n > 1
Donner S(3). Vérifier que cette suite d’arcs correspond à une exécution de l’algorithme de Ford pour les
plus courts chemins d’origine a3 de G(3).
3. Montrer que les suites S(n) correspondent à une exécution de l’algorithme de Ford pour les plus courts
chemins de G(n) issus de an .
4. Le nombre d’itérations de ces exécutions de l’algorithme de Ford correspond à la longueur des suites S(n)
puisque chaque itération fondamentale de l’algorithme correspond à l’examen d’un arc. Nous notons T (n)
le nombre d’arcs de S(n).
Montrer que T (n) ≥ 2n . En déduire que la complexité de l’algorithme de Ford est Ω(2n ).

2.2 Application des algorithmes

1. Appliquer l’algorithme de Ford pour obtenir les plus courts chemins issus du sommet 1.
2. Appliquer l’algorithme de Ford-Bellman pour obtenir les plus courts chemins issus du sommet 1.
3. Représenter l’arborescence des plus courts chemins obtenue.
5.3 Transformation de graphe

1. Peut-on appliquer l’algorithme de Dijkstra ou celui de Bellman dans le graphe G de la figure ? (justifier)
2. Appliquer l’algorithme de votre choix le graphe G pour trouver un chemin de valeur minimale λ(i) du
sommet 1 vers chaque sommet i (i ∈ {1, . . . , 6}). On tracera l’arborescence des chemins optimaux.
3. Construire le graphe G0 à partir du graphe G de la façon suivante : Pour tout arc (i, j) de G, on remplace
la valeur wij sur (i, j) par Lij = wij + λ(i) − λ(j). Quelle est l’intérêt d’une telle transformation ?
4. Appliquer l’algorithme de Dijkstra dans G0 pour trouver les plus courts chemins de 3 vers les autres
sommets.
5. Calculer les valeurs correspondantes dans G mais sans faire la somme des valeurs des arcs constituant les
chemins optimaux trouvés précédemment. Indice : utiliser les formules de la question 3.

5.4 Circuit de longueur minimale


Cet exercice illustre comment il est possible d’utiliser l’algorithme de Dijkstra pour calculer la longueur d’un
plus court circuit passant par un arc donné dans un graphe orienté fortement connexe valué positivement.
1. Soit G = (V, E) un graphe fortement connexe arc-valué par c : V → R+. Montrer que les circuits
élémentaires sont dominants pour le problème du plus court circuit.
2. Soit e = (v, w) ∈ E un arc de G. On note G(e) l’ensemble des circuits passant par e et γ(e) un plus court
circuit de G(e). Montrer que γ(e) existe.
3. Soit µ(e) le chemin obtenu en retirant e de γ(e). Montrer que µ(e) est un plus court chemin de w à v.
4. Donner une adaptation de l’algorithme de Dijkstra pour calculer γ(e) étant donnés G, c, e.

Vous aimerez peut-être aussi