Algorithme de Ford-Bellman
Donnons un graphe orienté pondéré G avec n sommets et m arêtes, et quelques sommets de départ v > . Il est nécessaire de trouver les longueurs des chemins les plus courts du sommet v à tous les autres sommets.
Comme Dijkstra, Ford-Bellman recherche la distance entre le sommet 1 et tous les autres, mais fonctionne avec des arêtes négatives.
;
L'algorithme Ford-Bellman lui-même se compose de plusieurs phases ( n-1). A chaque phase, toutes les arêtes du graphe sont examinées, et l'algorithme essaie de relaxer le long de chaque arête (a, b) du coût c. Détente le long d'un bord — ceci est une tentative d'améliorer la signification de d[a] la valeur d[b] + c. En fait, cela signifie que nous essayons d'améliorer la réponse pour le sommet en utilisant l'arête et la réponse actuelle pour le haut.
Le tableau d est un tableau des longueurs les plus courtes à partir du sommet de départ, tout comme dans Dijkstra, nous le remplissons initialement avec le plus grand nombre possible, sauf pour le sommet de départ, dans lequel vous devez mettre 0.
Pour stocker les arêtes, ce n'est pas une matrice d'adjacence ou une matrice de poids qui est utilisée, mais une liste qui indique de quel nœud part l'arête ( from), vers laquelle elle vient ( to) et son poids (coût).
bord de la structure {
int de, à, coût ;
} ;
vecteur<bord> bords;
La constante INF dénote le nombre "infini" - il doit être choisi de telle sorte qu'il dépasse évidemment toutes les longueurs de chemin possibles.
L'implémentation la plus simple de l'algorithme :
d[v] = 0 ;
pour (int i=0; i<n-1; ++i)
pour (int j=0; j<m; ++j)
si (d[bords[j].de] <INF)
d[bords[j].to] = min(d[bords[j].to], d[bords[j].from] + bords[j].cost);
ou un peu plus court en utilisant la syntaxe C++11 :
d[v] = 0 ;
pour (int i=0 ; i< n-1 ; ++i)
pour (arête j : arêtes)
si (d[j.from] <INF)
d[j.to] = min(d[j.to], d[j.from] + j.cost);
Exemple de travail
Prenez un graphe orienté simple à 5 nœuds, 4 arêtes de poids égal à 1.
Introduisons une liste d'arêtes dans cet ordre.
4 5 1
3 4 1
2 3 1
1 2 1
Valeurs initiales dans le tableau des longueurs les plus courtes :
où inf doit être un entier apparié qui est toujours supérieur au poids de l'arête.
Après le 1er passage
Après le 2e passage
Après le 3ème passage
Après le 4ème passage
Si nous alimentions les arêtes dans l'ordre de 1 à la dernière, nous pourrions trouver les longueurs les plus courtes après la 1ère passe.
|