Pourquoi les cycles des bords négatifs sont-ils autorisés dans les algorithmes de ford bellman alors qu'aucun bord négatif n'est autorisé dans les algorithmes de dijkstra?pourquoi bord négatif autorisé dans les algorithmes de ford de bellman?
Toutes vos questions à ce jour semblent être des questions en classe. Veuillez vous référer à 1.) Manuel et 2.) Notes de cours. vous trouverez la réponse clairement documentée dans 1 ou dans les deux endroits.
Autorisé? L'algorithme de Bellman-Ford permet arêtes distinctes avec des poids négatifs (non pris en charge dans l'algorithme de Dijkstra), mais ni l'algorithme "permet" négatif cycles. Le problème du chemin le plus court n'a aucun sens en présence d'un cycle négatif, il n'y a donc pas de manière significative de "permettre" des cycles négatifs dans un tel algorithme.
L'algorithme de Bellman-Ford peut être utilisé pour détecter la présence d'un cycle négatif et annuler l'exécution (annuler, car aucune solution correcte n'existe dans ce cas).
Vous voulez savoir pourquoi son algorithme peut gérer les bords négatifs alors que Dijkstra ne le peut pas? –