Ce n'Bellman-Ford algorithme détecte? Poids négatif ou négatif cycle?
Si nous sommes donné un graphe, à partir de Maintenant, nous sommes à calculer le plus court chemin. Maintenant , Si un avantage a un poids négatif , mais il est de pointe à dos-bord pour en revenir à ce bord en arrivant à la destination que je veux dire, si il n'y a pas de cycle, alors nous n'avons pas un cycle négatif. Mais le ici dans Wikipedia l'algorithme qui s'exécute à partir de la source à nouveau ainsi il détecte un négatif bord de leur poids, mais pas un cycle négatif. Ma Question est, Comment déterminer un cycle négatif?
OriginalL'auteur Tamim Addari | 2013-11-04
Vous devez vous connecter pour publier un commentaire.
Un poids négatif cycle est un cycle avec des poids que la somme d'un nombre négatif. La Bellman-Ford algorithme propage à bonne distance des estimations pour tous les nœuds dans un graphe V-1 étapes, à moins qu'il y est un cycle de poids négatif. Si il y a un cycle de poids négatif, vous pouvez aller sur la détente de ses nœuds indéfiniment. Par conséquent, la capacité à se détendre un bord après V-1 étapes est un test pour la présence d'un cycle de poids négatif, comme on le voit dans le Wikipedia algorithme. Ainsi, le Bellman-Ford algorithme de tests pour poids négatif des cycles.
OriginalL'auteur James Candy