Différences

Ci-dessous, les différences entre deux révisions de la page.

--- nsi:terminales:dynamique:bellman-ford [2023/02/03 18:30] – supprimée - modification externe (Unknown date) 127.0.0.1
+++ nsi:terminales:dynamique:bellman-ford [2023/02/03 20:34] (Version actuelle) – goupillwiki
@@ Ligne 1: / Ligne 1: @@
+====== Algorithme de Bellman - Ford ======
+[[https://fr.wikipedia.org/wiki/Algorithme_de_Bellman-Ford|Fiche Wikipedia]]
+Comme l'algorithme de [[nsi:terminales:graphes:dijkstra|Dijkstra]], il s'agit d'une recherche de plus court chemin dans un graphe.
+À titre d'exemple, nous considérerons le graphe suivant :
+{{ :nsi:terminales:graphes:graphe_reseau_1.svg |}}
+===== Principe =====
+On considère un sommet ''s0'' qui est l'indice du sommet de départ.
+On crée un tableau ''%%dist[s][k]%%'', où ''s'' est l'indice d'un sommet et ''k'' un entier. ''%%dist[s][k]%%'' représente la longueur du plus court chemin depuis ''s0'' jusqu'à ''s'' et n'utilisant, au plus, que ''k'' arêtes.
+==== Initialisation ====
+Si on ne s'autorise aucune arête, seul le point de départ peut être atteint, à coût nul. Les autres sont inatteignables.
+  * ''%%dist[s0][0] = 0%%''
+  * ''%%dist[s][0] = float('inf')%%'' pour ''s != s0''
+==== Itération ====
+  * Pour chaque ''k'' dans 1, 2, ...
+    * pour chaque ''s'', on calcule les ''%%dist[s][k]%%''.
+On utilise la règle suivante : ''%%dist[s][k]%%'' est la plus petite valeur entre
+  * ''%%dist[s][k-1]%%'',
+  * le minimum des ''%%dist[si][k-1] + poids(si,s)%%'' où ''si'' est un antécédent de ''s'' et ''poids(si,s)'' est la pondération de l'arc ''si'' -> ''s''.
+==== Fin ====
+Dans un graphe d'ordre ''n'', si on ne fait pas de boucles, un chemin parcourt au plus ''n'' sommets. Un parcours de ''n'' sommets nécessite le passage de ''n-1'' arêtes.
+On peut donc arrêter l'itération sur ''k'' quand ''k == n-1''.
+==== Réponse ====
+Si le sommet final demandé est ''sf'', il faut renvoyer ''%%dist[sf][n-1]%%''.
+==== Enregistrer le chemin ====
+Dans ce qui précède, nous avons considéré que ''%%dist[s][k]%%'' ne contient que la longueur d'un chemin. On peut si on le souhaite demander que ''%%dist[s][k]%%'' contienne également la liste des sommets à visiter pour ce chemin. On peut aussi construire un autre tableau ''%%chemin[s][k]%%'' pour stocker ces chemins.
+<WRAP tip>
+J'ai décrit ''dist'' comme un tableau et alors les ''s'' doivent être des indices. Mais si on préfère que ''s'' soit l'étiquette d'un sommet, on peut construire ''dist'' sous forme d'un dictionnaire.
+</WRAP>
+===== Exemple =====
+{{ :nsi:terminales:graphes:graphe_reseau_1.svg |}}
+Envisageons le chemin R1 -> R7
+^ k ^ R1 ^ R2       ^ R3       ^ R4       ^ R5       ^ R6       ^ R7       ^
+| 1 | 0  | $\infty$ | $\infty$ | $\infty$ | $\infty$ | $\infty$ | $\infty$ |
+| 2 | 0  | 4        | 1        | 3        | $\infty$ | $\infty$ | $\infty$ |
+| 3 | 0  | 4        | 1        | 2        | 6        | 6        | 8        |
+| 4 | 0  | 4        | 1        | 2        | 6        | 5        | 8        |
+| 5 | 0  | 4        | 1        | 2        | 6        | 5        | 8        |
+| 6 | 0  | 4        | 1        | 2        | 6        | 5        | 8        |
+== Remarques ==
+  * De la ligne $k = 4$ à la ligne $k = 5$, il n'y a pas de changement. On pourrait s'arrêter là.
+  * Observons à titre d'exemple le calcul pour R6. En ligne $k = 2$, on avait 3 comme meilleure distance pour R4. Cela nous donnait en ligne $k = 3$ un meilleure distance de 6 pour R6.\\ Mais en ligne $k = 3$, la meilleure distance pour R4 passe à 2. Cela permet une amélioration, en ligne $k = 4$, de la meilleure distance pour R6.
+  * Il suffit d'observer les colonnes qui changent. Par exemple, si la colonne R3 change, il faut consulter les colonnes R5 et R1 pour voir si elles ne changeront pas non plus.1
+<WRAP tip>
+Chaque sommet n'a pas à considérer l'ensemble du graphe. Il n'a à connaître que les scores des ses voisins. Si on imagine les sommets comme des machines indépendantes, on peut laisser chaque machine construire sa propre colonne. Chaque fois qu'une machine change sa colonne, elle en informe ses voisins qui peuvent se mettre à jour. C'est le principe de la configuration automatique d'un réseau.
+Au bout d'un moment, il n'y a plus aucun changement, le tableau se stabilise.
+</WRAP>
+<WRAP box>
+===== Implémentation =====
+Implémentez l'algorithme de Bellman - Ford
+</WRAP>
+===== Variante =====
+On voudrait obtenir une table de routage pour l'ensemble du graphe en simulant le comportement décrit dans l'encadré plus haut : les sommets communiquent à leurs voisins les améliorations faites à leur chemins.
+Cette table aurait la forme suivante :
+  * ''%%table[s1][s2]%%'' est un tableau (ou dictionnaire),
+  * ''s1'' est un sommet de départ et ''s2'' un sommet d'arrivée,
+  * ''%%table[s1][s2]%%'' contient une paire formée de :
+    * le sommet ''n'' vers lequel ''s1'' doit envoyer ses messages à destination de ''s2''
+    * la distance ''d'' du chemin de ''s1'' à ''s2''
+On peut initialiser le tableau ''table'' en mettant la paire ''%%table[s][s] = (s, 0)%%'' pour tous les sommets ''s'' du graphe.
+On met en place aussi une file ''changements'' qui indique les routes qui ont subit un changement. ''changements'' contient des paires ''(s1, s2)''. Une telle paire signifie que ''s1'' a vu s'améliorer sa route pour ''s2''.
+On initialise ''changements'' en y plaçant des paires ''(s,s)'' pour tous les sommets.
+Enfin on lance une boucle : Tant que ''changements'' n'est pas vide :
+  * on défile la prochaine paire ''(s1,s2)''\\ cela veut dire que l'on a une amélioration de la route ''s1'' -> ''s2'' et qu'on voudrait en faire profiter les voisins de ''s1''
+  * on parcours tous les antécédants ''v'' de ''s1'' et pour chacun :
+    * on lit le contenu ''n, d'' de ''%%table[v][s2]%%''.\\ Cela représente le meilleur chemin actuel de ''v'' à ''s2''.\\ On veut savoir si la nouveauté de ''s1'' -> ''s2'' permet d'améliorer ''v'' -> ''s2''
+    * si ''n'' est déjà égal à ''s1'', il n'y aura de toute façon pas de changement, on peut passer à la suite.
+    * on calcule ''d1'' la distance égale à la somme du coût de ''s1'' -> ''s2'' que l'on vient d'améliorer, avec le poids de l'arête ''s1'' -- ''v''.
+    * si ''d1 < d'', la nouvelle route est donc meilleure. On modifie donc ''%%table[v][s2]%%'' et on y écrit ''%%(s1, d1)%%'', ce qui signifie que si ''v'' doit rejoindre ''s2'', alors il faut passer par ''s1''.