Algorithme de Bellman - Ford

Comme l'algorithme de Dijkstra, il s'agit d'une recherche de plus court chemin dans un graphe.

À titre d'exemple, nous considérerons le graphe suivant :

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.

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.

Exemple

Envisageons le chemin R1 → R7

k	R2	R3	R4	R5	R6	R7
1	$\infty$	$\infty$	$\infty$	$\infty$	$\infty$	$\infty$
2	4	1	3	$\infty$	$\infty$	$\infty$
3	4	1	2	6	6	8
4	4	1	2	6	5	8
5	4	1	2	6	5	8
6	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

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.

Implémentation

Implémentez l'algorithme de Bellman - Ford

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.