Algorithme Bellman-Ford - Pourquoi les bords peuvent-ils être mis à jour dans le désordre?

L' algorithme de Bellman-Ford détermine le chemin le plus court d'une source à tous les autres sommets. Initialement, la distance entre et tous les autres sommets est définie sur . Ensuite, le chemin le plus court de à chaque sommet est calculé; cela continue pour les itérations . Mes questions sont: $s$ $s$ $\infty$ $s$ $|V|-1$

Pourquoi faut-il des itérations ? $|V|-1$
Serait-il important que je vérifie les bords dans un ordre différent?
Disons, si je vérifie d'abord les bords 1,2,3, mais à la deuxième itération, je vérifie 2,3,1.

MIT Professeur Eric a dit l'ordre n'a pas d' importance, mais cette embrouille me: ne l'algorithme mettre à jour correctement un nœud basé sur le bord si sa valeur dépendait du bord mais est mis à jour après ? $x_2$ $x_1$ $x_1$ $x_2$

algorithms shortest-path user1675999
la source

Quelle implémentation considérez-vous? La programmation dynamique n'a pas de problème de commande, évidemment; pour d'autres, cela peut être non trivial.

Raphael

Réponses:

Considérez le chemin le plus court de à , . Ce chemin se compose d'au plus arêtes, car répéter un sommet dans un chemin le plus court est toujours une mauvaise idée (ou au moins il y a un chemin le plus court qui ne répète pas les sommets), si nous n'avons pas de cycles de poids négatifs . $s$ $t$ $s, v_1, v_2, \dots, v_k, t$ $|V|-1$

Au premier tour, nous savons que le bord sera détendu, donc l'estimation de la distance pour sera correcte après ce tour. Notez que nous n'avons aucune idée de ce qu'est à ce stade, mais comme nous avons assoupli tous les bords, nous devons également avoir assoupli celui-ci. Au deuxième tour, nous nous détendons à un moment donné. Nous n'avons toujours aucune idée de ce que sont ou , mais nous savons que leurs estimations de distance sont correctes. $(s, v_1)$ $v_1$ $v_1$ $(v_1, v_2)$ $v_1$ $v_2$

En répétant cela, après quelques tours , nous avons relâché , après quoi l'estimation de la distance pour est correcte. Nous n'avons aucune idée de ce que est jusqu'à ce que l'algorithme entier soit terminé, mais nous savons qu'il se produira à un moment donné (en supposant qu'il n'y ait pas de cycles de poids négatifs). $k+1$ $(v_k, t)$ $t$ $k$

Ainsi, l'observation cruciale est qu'après le tour , le ème nœud du chemin le plus court doit avoir son estimation de distance réglée à la valeur correcte. Comme le chemin est au maximum long, les suffisent pour trouver ce chemin le plus court. Si unLe cycle change encore quelque chose, puis quelque chose d'étrange se passe: tous les chemins doivent déjà être «réglés» à leurs valeurs finales, nous devons donc avoir la situation où un cycle de poids négatif existe. $i$ $i$ $|V|-1$ $|V|-1$ $|V|$

Alex ten Brink
la source

J'ai un petit doute ici. Je pense que | v | -1 est le pire des nombres de tours après lesquels le chemin le plus court est calculé de s à t. Supposons que nous ayons les sommets s, v1, v2..vn, t. les arêtes sont choisies dans cet ordre, disons (s, v1), (v1, v2) .. (vn, t), puis dans une seule itération elle-même nous aurons le chemin le plus court de s à t. Ceci est juste pour la compréhension et termes pratiques, nous ne connaissons pas l'ordre des arêtes sélectionnées et donc | v | -1 tours. Ai-je raison?

whokares

@whokares: oui, vous pourriez avoir de la chance et trouver le chemin le plus court au premier tour. Vous ne savez pas avec certitude jusqu'au dernier tour que la valeur que vous trouvez est vraiment le chemin le plus court, mais cela pourrait l'être. L'algorithme de Dijkstra `` provoque '' essentiellement cela: si tous les bords ont des poids non négatifs, alors la file d'attente prioritaire utilisée dans l'algorithme de Dijkstra `` prédit '' l'ordre dans lequel vous devez détendre les bords afin que vous trouviez tous les chemins les plus courts dans votre premier cycle de relaxations.

Alex ten Brink

Merci pour la mise à jour.Je l'ai. Dans l'un des documents, il est mentionné sous le titre <br> Diapositive 6: Un mauvais choix d'ordre de relaxation peut conduire à de nombreuses relaxations exponentielles: <br> Diapositive 8: Ordre "intelligent" des relaxations des bords <br>

whokares

Quel que soit l'ordre des arêtes à chaque itération, les chemins les plus courts seront calculés en | v | -1 itérations, n'est-ce pas? Pourquoi dit-il exponentiel? Est-ce qu'il veut dire que si nous choisissons le même ordre pour toutes les itérations que nous faisons normalement, le code de relaxation sera appelé mais la mise à jour de l'étiquette pour un sommet peut se produire seulement moins de fois en raison de l'ordre, ce qui économise le processeur temps ?

whokares

@whokares: le premier algorithme qu'ils présentent (qui peut avoir un temps d'exécution exponentiel) ne détend pas tous les bords d'un round, mais trouve à la place un bord pour lequel une opération de relaxation changerait quelque chose et détend ce bord. Si vous continuez à faire cela et qu'il n'y a pas de cycle de poids négatif, alors finalement aucun bord ne vous aiderait plus et vous vous arrêtez. Cependant, parce que vous n'avez pas de tours et aucun ordre défini sur quel bord se détendre ensuite, vous pourriez finir par faire un nombre exponentiel de relaxations. L'algorithme amélioré qu'ils présentent est Bellman-Ford, qui a des tours.

Alex ten Brink

Le plus long chemin peut être sans cycles |V|. Nous commençons avec une source, nous avons donc déjà un chemin de longueur 1, nous avons donc besoin de |V| - 1plus de nœuds pour obtenir le chemin le plus long.

L'ordre n'a pas d'importance car chaque commande maintiendra l'invariant: après les nitérations, la valeur de chaque nœud est inférieure ou égale au coût du chemin de coût minimum sdu nœud contenant le plus de nbords.

Si, au début d'une itération, le coût est correct jusqu'aux nnœuds, alors à la fin de l'itération, il est correct jusqu'aux n+1nœuds. Une réorganisation peut entraîner un moindre coût pour certains nœuds avant qu'ils ne soient normalement mis à jour, mais ils seront finalement mis à jour de toute façon.

fgb
la source

Je ne sais pas si c'est juste moi, ou je ne peux pas vraiment visualiser ces faits facilement. Pour moi, je pense toujours qu'il pourrait y avoir des nœuds qui n'ont pas été mis à jour dans les itérations V-1.

user1675999

Non, vous avez | E | = | V | -1 arêtes lorsque vous avez | V | nœuds reliés par un chemin simple sans cycles. Et vous avez des itérations | V | -1, supprimez votre réponse car elle est incorrecte.

Sam

@sam Qui êtes-vous et qu'est-ce que tout ce que vous dites a à voir avec la réponse?

fgb