Algorithme de ford-bellman

Algorithme de Ford-Bellman

L'algorithme de Bellman-Ford (Bell-End-Ford) (Richard Bellman, Samuel End et Lester Ford) est un algorithme de programmation dynamique qui permet de trouver des plus courts chemins, depuis un sommet source donné, dans un graphe orienté pondéré. Contrairement à l'algorithme de Dijkstra, qui ne peut être utilisé que lorsque tous les arcs ont des poids positifs ou nuls, l'algorithme de Bellman-Ford autorise la présence de certains arcs de poids négatif et permet de détecter l'existence d'un circuit absorbant, c'est-à-dire de poids total négatif, accessible depuis le sommet source.

La complexité de l'algorithme est, dans le pire des cas, en O(nm) pour un graphe avec n sommets et m arcs (ce qui correspond à une complexité en O(n³) pour un graphe simple dense).

 booléen Bellman_Ford( G, s) 
 
   initialisation ( G, s)  // les poids de tous les sommets sont mis à +infini 
                           // le poids du sommet initial à 0
   pour i=1 jusqu'à Nombre de sommets -1 faire 
    |    pour chaque arc (u, v) du graphe faire 
    |     |  paux := poids(u) + poids(arc(u, v)); 
    |     |  si paux < poids(v) alors 
    |     |    |  pred(v) := u; 
    |     |    |  poids(v) := paux; 
   pour chaque arc (u, v) du graphe faire 
    |   si poids(u) + poids(arc(u, v)) <poids(v) alors 
    |     retourner faux 
   retourner vrai 

Implémentation C++

  void BFinitialisation( UnSommet  us){   // initialisation d'un sommet
    us.LeSommet.valeur = Infini;
    us.LeSommet.couleur = blanc;
    us.LeSommet.pred = null;
  }

  boolean parcoursAretes( ){ 
       // retourne true s'il y a eu au moins une modification du poids d'un sommet, 
    // et false sinon.
   boolean res = false;
   for( Iterator<UnSommet> it1 = lesSommets.iterator(); it1.hasNext(); )
      for(Iterator <Arete> ia = it1.next().lesAretes.iterator(); 
                                                ia.hasNext(); ){
           Arete a = ia.next();
           double p = a.depart.leSommet.valeur + a.valeur;
           if (p <  a.arrivee.leSommet.valeur){
               a.arrivee.leSommet.valeur = p;
               a.arrivee.leSommet.predecesseur = a.depart.leSommet;
               res = true;
            }
       }
    return res;
  }

  boolean BellmannFord( int d ){
   // initialisations
   for(Iterator<UnSommet> it = lesSommets.iterator(); it.hasNext(); ) {
        BFinitialisation(it.next()); 

   UnSommet us = chercher(d);
   us.leSommet.valeur = 0;
   for(int i=0; i<lesSommets.size()-1; ++i)
        if(!parcoursAretes()) return true;
   // existe-t-il un circuit de poids négatif ?
   return !parcoursAretes();
  }  

Voir aussi

• Algorithme de Dijkstra
• Algorithme de Dantzig-Ford

Ce document provient de « Algorithme de Ford-Bellman ».