QCM - Plus courts chemins

QCM - Plus courts chemins

Question 1. L'algorithme de Dijkstra permet de calculer :

Les plus courts chemins avec poids négatifsLes plus courts chemins depuis une source avec poids positifs ou nulsUn arbre couvrant de poids minimumLes composantes fortement connexes

Question 2. L'algorithme de Bellman-Ford permet de :

Calculer les plus courts chemins avec poids négatifs (sans cycle négatif)Trouver un cycle hamiltonienCalculer un couplage maximumTrier les sommets par degré

Question 3. La complexité de Dijkstra avec un tas binaire est :

$O(n^2)$$O(n + p)$$O((n + p) \log n)$$O(n^3)$

Question 4. La complexité de Bellman-Ford est :

$O(n + p)$$O(n \cdot p)$$O(n^2)$$O(n^3)$

Question 5. L'algorithme de Floyd-Warshall calcule :

Les plus courts chemins depuis une sourceLes plus courts chemins entre toutes les paires de sommetsUn arbre couvrant minimumLes composantes connexes

Question 6. La complexité de Floyd-Warshall est :

$O(n^2)$$O(n \cdot p)$$O(n^3)$$O(n^2 \log n)$

Question 7. Dijkstra ne fonctionne pas avec des poids négatifs car :

Il ne peut pas trier les arêtesUne fois un sommet traité, sa distance peut encore diminuer avec un poids négatifIl nécessite un graphe connexeIl ne gère pas les cycles

Question 8. Pour détecter un cycle de poids négatif avec Bellman-Ford, on effectue :

n-1 passes de relaxationUne n-ième passe qui ne devrait rien modifier s'il n'y a pas de cycle négatifUn parcours BFSUne recherche de composantes fortement connexes

Question 9. L'opération de relaxation d'une arête $(u, v)$ consiste à :

Supprimer l'arête $(u, v)$Mettre à jour $d[v] = \min(d[v], d[u] + w(u,v))$Inverser le sens de l'arêteAjouter un nouveau sommet

Question 10. L'algorithme de Johnson pour les plus courts chemins entre toutes paires utilise :

Uniquement DijkstraUniquement Bellman-FordBellman-Ford puis $n$ appels à Dijkstra après repondérationFloyd-Warshall puis Dijkstra