En prévision du début du cours «Algorithmes pour les développeurs», ils ont préparé une autre traduction d'un article intéressant.
Problème : étant donné un graphe et un sommet de src initial dans un graphe, il est nécessaire de trouver les chemins les plus courts de src à tous les sommets d'un graphe donné. Le graphique peut contenir des bords avec des poids négatifs.
Nous avons déjà discuté l'algorithme de Dijkstra comme un moyen de résoudre ce problème. L'algorithme de Dijkstra est un algorithme gourmand, et sa complexité est O (VLogV) (en utilisant le tas de Fibonacci). Cependant, Dijkstra ne fonctionne pas pour les graphiques avec des poids de bord négatifs, alors que Bellman-Ford l'est complètement. L'algorithme de Bellman-Ford est encore plus simple que l'algorithme de Dijkstra et convient bien aux systèmes distribués. En même temps, sa complexité est
O (VE) , ce qui est plus que l'indicateur de l'algorithme de Dijkstra.
Recommandation : avant de passer à l'affichage de la solution, essayez de vous
exercer .
Algorithme
Les étapes suivantes sont détaillées.
Entrée : Graphique et sommet initial
src .
Sortie : La distance la plus courte à tous les sommets de src. Si un cycle de poids négatif se produit, les distances les plus courtes ne sont pas calculées, un message s'affiche indiquant la présence d'un tel cycle.
- À cette étape, les distances du sommet initial à tous les autres sommets sont initialisées comme infinies, et la distance à src elle-même est supposée être 0. Un tableau
dist[] taille |V| avec toutes les valeurs égales à l'infini, à l'exception de l'élément dist[src] , où src est le sommet d'origine. - La deuxième étape calcule les distances les plus courtes. Les étapes suivantes doivent être effectuées
|V| -1 fois, où |V| - le nombre de sommets dans ce graphique.
- Effectuez l'action suivante pour chaque bord uv :
Si dist[v] > dist[u] + uv , mettez à jour dist[v]
dist [v] = dist [u] + uv
- Dans cette étape, il est indiqué si un cycle de poids négatif est présent dans le graphique. Pour chaque bord uv , procédez comme suit:
- Si
dist[v] > dist[u] + uv , alors le graphique contient un cycle de poids négatif.
L'idée de l'étape 3 est que l'étape 2 garantit la distance la plus courte si le graphique ne contient pas de cycle de poids négatif. Si nous repassons sur tous les bords et obtenons un chemin plus court pour l'un des sommets, ce sera un signal de la présence d'un cycle de poids négatif.
Comment ça marche? Comme dans d'autres tâches de programmation dynamique, l'algorithme calcule les chemins les plus courts de bas en haut. Tout d'abord, il calcule les distances les plus courtes, c'est-à-dire les chemins d'une longueur ne dépassant pas un bord. Ensuite, il calcule les chemins les plus courts avec une longueur ne dépassant pas deux bords et ainsi de suite. Après la ième itération de la boucle externe, les chemins les plus courts avec une longueur ne dépassant pas
i arêtes sont calculés. Dans tout chemin simple, il peut y avoir un maximum de
| V | -1 bords, de sorte que la boucle externe s'exécute exactement
| V | -1 fois. L'idée est que si nous calculons le chemin le plus court avec pas plus de
i bords, alors itérer sur tous les bords garantit d'obtenir le chemin le plus court avec pas plus de
i + 1 bords (la preuve est assez simple, vous pouvez vous référer à
cette conférence ou
conférence vidéo du MIT )
Exemple
Regardons l'algorithme dans l'exemple de graphique suivant. Images prises
d'ici .
Soit le sommet initial égal à 0. Prenez toutes les distances comme infinies, à l'exception de la distance jusqu'à
src . Le nombre total de sommets dans le graphique est de 5, donc toutes les arêtes doivent aller 4 fois.
Laissez les côtes être travaillées dans l'ordre suivant: (B, E), (D, B), (B, D), (A, B), (A, C), (D, C), (B, C), ( E, D). Nous obtenons les distances suivantes lorsque le passage le long des côtes a été effectué pour la première fois. La première ligne montre les distances initiales, la deuxième ligne montre les distances lorsque les bords (B, E), (D, B), (B, D) et (A, B) sont traités. La troisième ligne indique la distance de traitement (A, C). La quatrième ligne montre ce qui se passe lorsque (D, C), (B, C) et (E, D) sont traités.
La première itération garantit que tous les chemins les plus courts ne sont pas plus longs que le chemin d'un bord. Nous obtenons les distances suivantes lorsque le deuxième passage sur tous les bords est terminé (la dernière ligne affiche les valeurs finales).
La deuxième itération garantit que tous les chemins les plus courts ont une longueur d'au plus 2 bords. L'algorithme parcourt tous les bords 2 fois de plus. Les distances sont minimisées après la deuxième itération, de sorte que les troisième et quatrième itérations ne mettent pas à jour les valeurs de distance.
Réalisation:
Valeurs de sortie:
Remarques:- Les poids négatifs se retrouvent dans diverses applications graphiques. Par exemple, au lieu d'augmenter le coût d'un chemin, nous pouvons bénéficier en suivant un chemin spécifique.
- L'algorithme de Bellman-Ford fonctionne mieux pour les systèmes distribués (mieux que l'algorithme de Dijkstra). Contrairement à Dijkstra, où nous devons trouver la valeur minimale de tous les sommets, dans Bellman Ford, les arêtes sont considérées une par une.
Exercices:- L'algorithme Bellman-Ford standard signale les chemins les plus courts uniquement s'il n'a pas de cycles de poids négatif. Modifiez-le afin qu'il signale les chemins les plus courts même s'il existe un tel cycle.
- Peut-on utiliser l'algorithme de Dijkstra pour trouver les chemins les plus courts dans un graphique avec des poids négatifs? Il existe une telle idée: calculer la valeur de poids minimum, ajouter une valeur positive (égale à la valeur absolue de la valeur de poids minimum) à tous les poids et exécuter l'algorithme de Dijkstra pour le graphique modifié. Un tel algorithme fonctionnera-t-il?
Implémentation simple de l'algorithme Bellman-FordSources:www.youtube.com/watch?v=Ttezuzs39nken.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithmwww.cs.arizona.edu/classes/cs445/spring07/ShortestPath2.prn.pdf