Algorithme de Bellman-Ford - Bellman–Ford algorithm

Algorithme de Bellman-Ford

Classer	Problème de plus court chemin à source unique (pour les graphes orientés pondérés)
Structure de données	Graphique
Performances dans le pire des cas	${\displaystyle \Thêta (|V||E|)}$
Le meilleur cas la performance	${\displaystyle \Thêta (|E|)}$
Complexité spatiale dans le pire des cas	${\displaystyle \Thêta (|V|)}$

L' algorithme de Bellman-Ford est un algorithme qui calcule les chemins les plus courts d'un seul sommet source à tous les autres sommets d'un digraphe pondéré . Il est plus lent que l'algorithme de Dijkstra pour le même problème, mais plus polyvalent, car il est capable de gérer des graphiques dans lesquels certains des poids de bord sont des nombres négatifs. L'algorithme a été proposé pour la première fois par Alfonso Shimbel ( 1955 ), mais porte plutôt le nom de Richard Bellman et Lester Ford Jr. , qui l'ont publié en 1958 et 1956 , respectivement. Edward F. Moore a également publié une variante de l'algorithme en 1959 , et pour cette raison, il est aussi parfois appelé algorithme de Bellman-Ford-Moore .

Les poids de bord négatifs se retrouvent dans diverses applications des graphes, d'où l'utilité de cet algorithme. Si un graphe contient un « cycle négatif » (c'est-à-dire un cycle dont la somme des arêtes est une valeur négative) accessible depuis la source, alors il n'y a pas de chemin le moins cher : tout chemin qui a un point sur le cycle négatif peut être rendu moins cher en encore une promenade autour du cycle négatif. Dans un tel cas, l'algorithme Bellman-Ford peut détecter et signaler le cycle négatif.

Algorithme

Dans cet exemple de graphe, en supposant que A est la source et que les bords sont traités dans le pire ordre, de droite à gauche, il faut le | V |−1 ou 4 itérations pour que les estimations de distance convergent. A l'inverse, si les arêtes sont traitées dans le meilleur ordre, de gauche à droite, l'algorithme converge en une seule itération.

Comme l'algorithme de Dijkstra , Bellman-Ford procède par relaxation , dans laquelle les approximations de la distance correcte sont remplacées par de meilleures jusqu'à ce qu'elles finissent par atteindre la solution. Dans les deux algorithmes, la distance approximative à chaque sommet est toujours une surestimation de la distance réelle et est remplacée par le minimum de son ancienne valeur et la longueur d'un chemin nouvellement trouvé. Cependant, l'algorithme de Dijkstra utilise une file d' attente prioritaire pour sélectionner avidement le sommet le plus proche qui n'a pas encore été traité, et effectue ce processus de relaxation sur tous ses bords sortants ; en revanche, l'algorithme de Bellman-Ford assouplit simplement toutes les arêtes, et le fait cette fois, où est le nombre de sommets dans le graphe. Dans chacune de ces répétitions, le nombre de sommets avec des distances correctement calculées augmente, d'où il s'ensuit que finalement tous les sommets auront leurs distances correctes. Cette méthode permet à l'algorithme de Bellman-Ford d'être appliqué à une classe d'entrées plus large que celle de Dijkstra. Les réponses intermédiaires dépendent de l'ordre des arêtes relâchées, mais la réponse finale reste la même. ${\style d'affichage |V|-1}$${\style d'affichage |V|}$

Bellman-Ford s'exécute dans le temps , où et sont respectivement le nombre de sommets et d'arêtes. ${\style d'affichage O(|V|\cdot |E|)}$ ${\style d'affichage |V|}$${\style d'affichage |E|}$

function BellmanFord(list vertices, list edges, vertex source) is

    // This implementation takes in a graph, represented as
    // lists of vertices (represented as integers [0..n-1]) and edges,
    // and fills two arrays (distance and predecessor) holding
    // the shortest path from the source to each vertex

    distance := list of size n
    predecessor := list of size n

    // Step 1: initialize graph
    for each vertex v in vertices do

        distance[v] := inf             // Initialize the distance to all vertices to infinity
        predecessor[v] := null         // And having a null predecessor
    
    distance[source] := 0              // The distance from the source to itself is, of course, zero

    // Step 2: relax edges repeatedly
    
    repeat |V|−1 times:
         for each edge (u, v) with weight w in edges do
             if distance[u] + w < distance[v] then
                 distance[v] := distance[u] + w
                 predecessor[v] := u

    // Step 3: check for negative-weight cycles
    for each edge (u, v) with weight w in edges do
        if distance[u] + w < distance[v] then
            error "Graph contains a negative-weight cycle"

    return distance, predecessor

En termes simples, l'algorithme initialise la distance à la source à 0 et tous les autres nœuds à l'infini. Ensuite, pour toutes les arêtes, si la distance jusqu'à la destination peut être raccourcie en prenant l'arête, la distance est mise à jour à la nouvelle valeur inférieure. A chaque itération i que les arêtes sont balayées, l'algorithme trouve tous les chemins les plus courts d'au plus i arêtes de longueur (et éventuellement certains chemins plus longs que i arêtes). Étant donné que le chemin le plus long possible sans cycle peut être des arêtes, les arêtes doivent être balayées plusieurs fois pour s'assurer que le chemin le plus court a été trouvé pour tous les nœuds. Un balayage final de toutes les arêtes est effectué et si une distance est mise à jour, alors un chemin d' arêtes de longueur a été trouvé qui ne peut se produire que s'il existe au moins un cycle négatif dans le graphique. ${\style d'affichage |V|-1}$${\style d'affichage |V|-1}$${\style d'affichage |V|}$

Preuve d'exactitude

La correction de l'algorithme peut être montrée par récurrence :

Lemme . Après i répétitions de la boucle for ,

• si Distance( u ) n'est pas l'infini, elle est égale à la longueur d'un chemin de s à u ; et
• s'il existe un chemin de s à u avec au plus i arêtes, alors Distance(u) est au plus la longueur du plus court chemin de s à u avec au plus i arêtes.

Preuve . Pour le cas de base de l'induction, considérons i=0et l'instant précédent la boucle for est exécutée pour la première fois. Ensuite, pour le sommet source, source.distance = 0, ce qui est correct. Pour les autres sommets u , , ce qui est également correct car il n'y a pas de chemin de la source à u avec 0 arêtes. u.distance = infinity

Pour le cas inductif, nous démontrons d'abord la première partie. Considérons un moment où la distance d'un sommet est mise à jour par v.distance := u.distance + uv.weight. Par hypothèse inductive, u.distanceest la longueur d'un chemin de la source à u . Alors u.distance + uv.weightest la longueur du chemin de la source à v qui suit le chemin de la source à u puis va à v .

Pour la deuxième partie, considérons un plus court chemin P (il peut y en avoir plusieurs) de la source à v avec au plus i arêtes. Soit u le dernier sommet avant v sur ce chemin. Ensuite, la partie du chemin de la source à u est un chemin le plus court de la source à u avec au plus i-1 arêtes, car si ce n'était pas le cas, alors il doit y avoir un chemin strictement plus court de la source à u avec au plus i- 1 arêtes, et on pourrait alors ajouter l'arête uv à ce chemin pour obtenir un chemin avec au plus i arêtes strictement plus court que P — une contradiction. Par hypothèse inductive, u.distanceaprès i −1 itérations est au plus la longueur de ce chemin de la source à u . Par conséquent, uv.weight + u.distanceest au plus la longueur de P . Dans la i ^ième itération, v.distanceobtient par rapport à uv.weight + u.distance, et est égale à si uv.weight + u.distanceest plus petit. Par conséquent, après i itérations, v.distanceest au plus la longueur de P , c'est-à-dire la longueur du chemin le plus court de la source à v qui utilise au plus i arêtes.

S'il n'y a pas de cycles de poids négatif, alors chaque chemin le plus court visite chaque sommet au plus une fois, donc à l'étape 3 aucune autre amélioration ne peut être apportée. Inversement, supposons qu'aucune amélioration ne puisse être apportée. Alors pour tout cycle de sommets v [0], ..., v [ k −1],

v[i].distance <= v[i-1 (mod k)].distance + v[i-1 (mod k)]v[i].weight

En sommant autour du cycle, les termes v [ i ].distance et v [ i −1 (mod k )].distance s'annulent, laissant

0 <= sum from 1 to k of v[i-1 (mod k)]v[i].weight

C'est-à-dire que chaque cycle a un poids non négatif.

Trouver des cycles négatifs

Lorsque l'algorithme est utilisé pour trouver les chemins les plus courts, l'existence de cycles négatifs est un problème, empêchant l'algorithme de trouver une réponse correcte. Cependant, comme il se termine lorsqu'il trouve un cycle négatif, l'algorithme de Bellman-Ford peut être utilisé pour des applications dans lesquelles c'est la cible à rechercher - par exemple dans les techniques d' annulation de cycle dans l' analyse de flux de réseau .

Applications en routage

Une variante distribuée de l'algorithme Bellman-Ford est utilisée dans les protocoles de routage à vecteur de distance , par exemple le protocole d'information de routage (RIP). L'algorithme est distribué car il implique un certain nombre de nœuds (routeurs) au sein d'un système autonome (AS) , un ensemble de réseaux IP généralement détenus par un FAI. Il se compose des étapes suivantes :

1. Chaque nœud calcule les distances entre lui-même et tous les autres nœuds de l'AS et stocke ces informations sous forme de table.
2. Chaque nœud envoie sa table à tous les nœuds voisins.
3. Lorsqu'un nœud reçoit des tables de distance de ses voisins, il calcule les itinéraires les plus courts vers tous les autres nœuds et met à jour sa propre table pour refléter tout changement.

Les principaux inconvénients de l'algorithme Bellman-Ford dans ce contexte sont les suivants :

• Il n'évolue pas bien.
• Les modifications de la topologie du réseau ne sont pas reflétées rapidement car les mises à jour sont réparties nœud par nœud.
• Comptez jusqu'à l'infini si des défaillances de liaison ou de nœud rendent un nœud inaccessible à partir d'un ensemble d'autres nœuds, ces nœuds peuvent passer indéfiniment à augmenter progressivement leurs estimations de la distance jusqu'à lui, et en attendant, il peut y avoir des boucles de routage.

Améliorations

L'algorithme de Bellman-Ford peut être amélioré dans la pratique (mais pas dans le pire des cas) par l'observation que, si une itération de la boucle principale de l'algorithme se termine sans apporter de modifications, l'algorithme peut être immédiatement terminé, car les itérations suivantes ne plus apporter de modifications. Avec cette condition de terminaison anticipée, la boucle principale peut dans certains cas utiliser beaucoup moins que | V | − 1 itérations, même si le pire cas de l'algorithme reste inchangé. Les améliorations suivantes maintiennent toutes la complexité temporelle dans le pire des cas. ${\style d'affichage O(|V|\cdot |E|)}$

Une variante de l'algorithme de Bellman-Ford connue sous le nom d'algorithme Shortest Path Faster , décrite pour la première fois par Moore (1959) , réduit le nombre d'étapes de relaxation qui doivent être effectuées dans chaque itération de l'algorithme. Si un sommet v a une valeur de distance qui n'a pas changé depuis la dernière fois que les arêtes de v ont été relâchées, alors il n'est pas nécessaire de relâcher les arêtes de v une seconde fois. De cette façon, à mesure que le nombre de sommets avec des valeurs de distance correctes augmente, le nombre dont les bords sortants qui doivent être relâchés à chaque itération diminue, conduisant à une économie de temps à facteur constant pour les graphes denses .

Yen (1970) a décrit une autre amélioration de l'algorithme de Bellman-Ford. Son amélioration attribue d'abord un ordre linéaire arbitraire sur tous les sommets, puis partitionne l'ensemble de toutes les arêtes en deux sous-ensembles. Le premier sous-ensemble, E _f , contient toutes les arêtes ( v _i , v _j ) telles que i < j ; le second, E _b , contient des arêtes ( v _i , v _j ) telles que i > j . Chaque sommet est visité dans l'ordre v ₁ , v ₂ , ..., v _{| V |} , relâchant chaque arête sortante de ce sommet dans E _f . Chaque sommet est ensuite visité dans l'ordre v _{| V |} , v _{| V |−1} , ..., v ₁ , relâchant chaque arête sortante de ce sommet dans E _b . Chaque itération de la boucle principale de l'algorithme, après la première, ajoute au moins deux arêtes à l'ensemble des arêtes dont les distances relaxées correspondent aux distances correctes du chemin le plus court : une de E _f et une de E _b . Cette modification réduit le nombre d'itérations dans le pire des cas de la boucle principale de l'algorithme de | V | − 1 à . ${\style d'affichage |V|/2}$

Une autre amélioration, par Bannister & Eppstein (2012) , remplace l'ordre linéaire arbitraire des sommets utilisé dans la deuxième amélioration de Yen par une permutation aléatoire . Ce changement rend le pire des cas pour l'amélioration de Yen (dans lequel les bords d'un chemin le plus court alternent strictement entre les deux sous-ensembles E _f et E _b ) très peu susceptible de se produire. Avec un ordre de sommets permuté de manière aléatoire, le nombre attendu d'itérations nécessaires dans la boucle principale est au plus . ${\style d'affichage |V|/3}$

Remarques

Les références

Sources originales

• Shimbel, A. (1955). Structure en réseaux de communication . Actes du Symposium sur les réseaux d'information. New York, New York : Polytechnic Press de l'Institut polytechnique de Brooklyn. p. 199-203.
• Bellman, Richard (1958). "Sur un problème de routage" . Trimestriel de Mathématiques Appliquées . 16 : 87-90. doi : 10.1090/qam/102435 . MR  0102435 .
• Ford, Lester R. Jr. (14 août 1956). Théorie des flux de réseau . Papier P-923. Santa Monica, Californie : RAND Corporation.
• Moore, Edward F. (1959). Le chemin le plus court à travers un labyrinthe . Proc. Internat. Symposium. Théorie de la commutation 1957, partie II. Cambridge, Massachusetts : Harvard Univ. Presse. p. 285-292. MR  0114710 .
• Yen, Jin Y. (1970). "Un algorithme pour trouver les routes les plus courtes de tous les nœuds sources vers une destination donnée dans les réseaux généraux" . Trimestriel de Mathématiques Appliquées . 27 (4) : 526-530. doi : 10.1090/qam/253822 . MR  0253822 .
• Bannister, MJ ; Eppstein, D. (2012). Accélération aléatoire de l'algorithme de Bellman-Ford . Algorithmique analytique et combinatoire (ANALCO12), Kyoto, Japon. p. 41–47. arXiv : 1111.5414 . doi : 10.1137/1.9781611973020.6 .

Sources secondaires

• Bang-Jensen, Jørgen; Gutin, Grégoire (2000). "Section 2.3.4: L'algorithme Bellman-Ford-Moore". Digraphs: Theory, Algorithms and Applications (Première édition). ISBN 978-1-84800-997-4.
• Schrijver, Alexandre (2005). « Sur l'histoire de l'optimisation combinatoire (jusqu'en 1960) » (PDF) . Manuel d'optimisation discrète . Elsevier : 1-68.
• Cormen, Thomas H. ; Leiserson, Charles E. ; Rivest, Ronald L. Introduction aux algorithmes . MIT Press et McGraw-Hill., Deuxième édition. MIT Press et McGraw-Hill, 2001. ISBN  0-262-03293-7 . Section 24.1 : L'algorithme de Bellman-Ford, pp. 588-592. Problème 24-1, p. 614-615. Troisième édition. MIT Press, 2009. ISBN  978-0-262-53305-8 . Section 24.1 : L'algorithme de Bellman-Ford, pp. 651-655.
• Heineman, George T. ; Policier, Gary ; Selkow, Stanley (2008). "Chapitre 6: Algorithmes de graphe". Algorithmes en bref . O'Reilly Media . 160-164. ISBN 978-0-596-51624-6.
• Kleinberg, Jon ; Tardos, Éva (2006). Conception d'algorithmes . New York : Pearson Education, Inc.
• Sedgewick, Robert (2002). "Section 21.7 : Poids de bord négatifs". Algorithmes en Java (3e éd.). ISBN 0-201-36121-3. Archivé de l'original le 2008-05-31 . Récupéré le 2007-05-28 .