Introduction
L’algorithme de Bellman-Ford est l’un des premiers algorithmes pour trouver le chemin le plus court entre une source et tous les autres sommets dans un digraphe sans cycles négatifs. C’est un algorithme de programmation dynamique qui relâche itérativement les arêtes du graphe. Dans cet article, un exemple est présenté pour illustrer cet algorithme !
Étapes clés de l’algorithme de Bellman-Ford
- Initialisation : Nous considérons d’abord que tous les sommets sont à une distance infinie de la source, sauf la source elle-même qui est bien sûr à une distance de 0. Notre objectif sera de mettre à jour ces poids de sommets de manière itérative.
- Relaxation : C’est là que la magie opère. Pour toutes les arêtes du graphe, nous vérifions si le poids du sommet source plus le poids de l’arête est inférieur au poids du sommet de destination. Si c’est le cas, nous mettons à jour le poids du sommet de destination. Par exemple, si la première arête a une valeur de 4, alors le poids de la destination deviendra 4.
- Terminaison : Nous répétons l’étape de relaxation
fois. En effet, le chemin le plus court entre deux sommets peut avoir au plus arêtes. Si nous avons encore un changement dans les poids après l’itération , cela signifie qu’il y a un cycle négatif dans le graphe.
L’algorithme de Bellman-Ford ne fonctionne pas avec des cycles négatifs
Un cycle négatif est un cycle dont le poids total est strictement négatif. Dans ce contexte, vous pouvez imaginer que si vous voulez aller de A à C, le chemin le plus court serait de revenir indéfiniment à A pour réduire le poids à l’infini. L’algorithme de Bellman-Ford ne fonctionne évidemment pas dans ce cas.
Cependant, comme nous avons déjà établi que l’algorithme n’a pas besoin de plus de
D’autres implémentations d’algorithmes implementation pourraient réduire le nombre d’itérations.
L’algorithme
Ok! Maintenant que nous avons vu les étapes clés de l’algorithme de Bellman-Ford, nous pouvons passer à l’implémentation de l’algorithme.
En style pseudo code python, l’algorithme peut être implémenté ainsi :
def bellman_ford(G: Graph, p: function(int, int) -> int, source: int) -> [prev: List[int], weight: List[int]]:
'''Pseudo code de bellman ford.
Args:
G : Graph : Un graphe sans cycles négatifs
p : function(int, int) -> int : Une fonction qui renvoie le poids de l'arête (u, v) en O(1)
source : int : L'indice du sommet source dans V
Returns:
prev : List[int] : Un tableau contenant le sommet précédent de chaque sommet.
weight : List[int] : Un tableau contenant, pour chaque sommet, le poids du chemin le plus court (somme des poids) de la source à ce sommet.
'''
# Initialisation
for v in G.vertices:
weight[v] = inf
prev[v] = '-'
weight[source] = 0 # De la source à la source, le poids est 0
for iter in [1, |V| - 1]: # Preuve de la condition d'arrêt sur wikipedia
for (u, v) in G.edges:
if weight[u] + p(u, v) < weight[v]:
weight[v] = weight[u] + p(u, v)
prev[v] = u
return prev, weight
L’étape de relachement if weight[u] + p(u, v) < weight[v]: est l’étape clé de l’algorithme. C’est là que l’algorithme met à jour le poids des sommets.
Exercice corrigé
Solution
Nous allons créer deux tableaux pour suivre les poids et les sommets précédents.
- Le premier tableau contiendra les poids des sommets. Il est équivalent à la distance la plus courte actuelle de la source au sommet.
- Le deuxième tableau contiendra le sommet précédent qui doit être pris pour atteindre le sommet actuel avec le chemin le plus court.
Tableau des poids
| Itération | s | 1 | 2 | 3 | 4 | p |
|---|---|---|---|---|---|---|
| Itér 0 | 0 | |||||
| Itér 1 | 0 | 4 | 2 | |||
| Itér 2 | 0 | 4 | 19 | -2 | 4 | |
| Itér 3 | 0 | 4 | 19 | -2 | 0 | 17 |
| Itér 4 | 0 | 4 | 19 | -2 | 0 | 17 |
| Itér 5 | 0 | 4 | 19 | -2 | 0 | 17 |
Aspect non déterministe
Vous pouvez avoir un résultat différent de celui présenté ici !
L’ordre dans lequel les arêtes sont relâchées peut changer le résultat. Par exemple, si le poids de l’arête 3 -> 4 est mis à jour avant le poids de l’arête 1 -> 4, le poids de 4 sera 0 au lieu de 4.
Cependant, cet algorithme convergera toujours vers le même résultat pour le poids, mais le chemin peut changer. (d’une ville à l’autre, vous pouvez probablement trouver deux routes différentes de même longueur).
Tableau des précédents
| Itération | s | 1 | 2 | 3 | 4 | p |
|---|---|---|---|---|---|---|
| Itér 0 | - | - | - | - | - | - |
| Itér 1 | - | s | - | s | - | - |
| Itér 2 | - | s | 1 | 1 | 3 | - |
| Itér 3 | - | s | 1 | 1 | 3 | 4 |
| Itér 4 | - | s | 1 | 1 | 3 | 4 |
| Itér 5 | - | s | 1 | 1 | 3 | 4 |
Pour calculer le chemin, prenez la dernière ligne du tableau des précédents.
De p, nous avons 4. De 4, nous avons 3. De 3, nous avons 1. De 1, nous avons s.
