Pour un graphe avec nœuds, une étudiante exécute l'algorithme de Bellman-Ford pour itérations. Elle effectue ensuite une itération supplémentaire et remarque que le chemin le plus court entre deux nœuds a diminué.
Qu'est-ce que cette observation suggère à propos du graphe ?

Question

Pour un graphe avec nœuds, une étudiante exécute l'algorithme de Bellman-Ford pour itérations. Elle effectue ensuite une itération supplémentaire et remarque que le chemin le plus court entre deux nœuds a diminué.

Qu'est-ce que cette observation suggère à propos du graphe ?

Answer

Le chemin le plus court entre les deux nœuds après l'itération supplémentaire est désormais optimal.

Answer

Le graphe    ne contient aucun cycle de poids négatif, et les résultats obtenus après    itérations correspondent aux chemins les plus courts.

Answer

L'algorithme de Bellman-Ford n'est pas adapté pour le graphe   .

Answer

Le graphe     contient un cycle de poids négatif.

Crowdly

Pour un graphe avec nœuds, une étudiante exécute l'algorithme de Bellman-F...

Want instant access to all verified answers on learning.devinci.fr?