Obtenir un cycle négatif avec Bellman Ford

20

Je dois trouver un cycle négatif dans un graphique pondéré dirigé. Je sais comment fonctionne l'algorithme de Bellman Ford et qu'il me dit s'il y a un cycle négatif atteignable. Mais il ne le nomme pas explicitement.

Comment puis-je obtenir le chemin réel du cycle?v1,v2,vk,v1

Après avoir appliqué l'algorithme standard, nous avons déjà effectué itérations et aucune autre amélioration ne devrait être possible. Si nous pouvons encore réduire la distance à un nœud, un cycle négatif existe.n-1

Mon idée est la suivante: puisque nous connaissons le bord qui peut encore améliorer le chemin et que nous connaissons le prédécesseur de chaque nœud, nous pouvons retracer notre chemin depuis ce bord jusqu'à ce que nous le rencontrions à nouveau. Maintenant, nous devrions avoir notre cycle.

Malheureusement, je n'ai trouvé aucun article me disant si c'est correct. Alors, ça marche vraiment comme ça?

Edit: Cet exemple prouve que mon idée est fausse. Étant donné le graphique suivant, nous exécutons Bellman-Ford à partir du nœud .1

entrez la description de l'image ici

Nous traitons les arêtes dans l'ordre . Après itérations, nous obtenons les distances des nœuds:une,b,c,n-1
1:-5
2:-30
3:-15

et table parent: a parent a parent a parent
13
23
32

Maintenant, en faisant la ième itération, nous voyons que la distance du nœud peut encore être améliorée en utilisant l'arête . Nous savons donc qu'il existe un cycle négatif et en fait partie.n1uneune

Mais, en retraçant notre chemin à travers la table parent, nous nous retrouvons coincés dans un autre cycle négatif et ne rencontrons plus jamais .c,une

Comment pouvons-nous résoudre ce problème?

Patrick Schmidt
la source

Réponses:

14

Vous avez raison pour la plupart. Encore un ajout. Lorsque vous remontez la chaîne précédente lorsque vous essayez de trouver le cycle, vous vous arrêtez lorsque vous atteignez le sommet de départ ou tout autre sommet qui a déjà été vu dans la chaîne précédente que vous avez vu jusqu'à présent. Fondamentalement, vous arrêtez et générez des sommets chaque fois que vous détectez un cycle lorsque vous reculez à l'aide des prédécesseurs.v1

En ce qui concerne les articles, une simple recherche sur Google donne Xiuzhen Huang: algorithmes de cycle de poids négatif . En prime, ils énumèrent aussi un autre algorithme pour trouver des cycles de poids négatifs qui sont pas accessibles à partir du sommet source .s

Paresh
la source
le lien est rompu.
human.js
Je viens d'utiliser l'idée du professeur Huang, mais je ne comprends pas pourquoi il ajoute à la fois un nouveau nœud source et une nouvelle cible ( s'et t'). Il me semblait qu'un nouveau nœud source, connecté à tous les sommets existants par une arête de n'importe quelle longueur, ferait remonter tous les cycles.
AbuNassar
0

Votre exemple ne contredit pas votre idée. En effet, vous avez trouvé un cycle négatif. Je pense que l'idée que votre exemple illustre est que le sommet source pourrait ne pas être un nœud dans le cycle négatif.

Spartan 117
la source