Français
Menu

Structures de données et algorithmes

Dans un graphe non orienté, les poids des arêtes (distances) sont S−A : 4, S−B : 1, A−B : 2, A−C : 1, B−C : 5, C−T : 3 et A−T : 6. Quelle réponse donne le plus court chemin de S à T trouvé par l'algorithme de Dijkstra et sa longueur ?

  1. AS→A→C→T, longueur 8
  2. BS→B→A→C→T, longueur 7
  3. CS→B→C→T, longueur 9
Afficher la réponse et l'explication

Réponse : B. S→B→A→C→T, longueur 7

L'algorithme de Dijkstra fixe de façon répétée le sommet le plus proche dont la distance n'est pas encore définitive, puis met à jour les distances de ses voisins. Depuis S (0), B est fixé à 1, et passer par B donne à A une distance de 1 + 2 = 3, plus courte que les 4 du trajet direct. Fixer A (3) donne à C 3 + 1 = 4 et à T 3 + 6 = 9, et fixer C (4) met à jour T à 4 + 3 = 7. Le plus court chemin est donc S→B→A→C→T, de longueur 7. S→A→C→T (8) est plus long parce qu'il prend directement S−A, et S→B→C→T (9) parce que B−C a un poids élevé de 5.

S'entraîner sur ce thème Retour au thème

Autres questions sur Structures de données et algorithmes

  1. Quelle condition sur le graphe est nécessaire pour que l'algorithme de Dijkstra trouve des plus courts chemins corrects ?
  2. Les tâches A à E ont les contraintes d'ordre « A avant C », « B avant C », « C avant D », « B avant E » et « E avant D ». Quel ordre satisfait toutes les contraintes (résultat d'un tri topologique) ?
  3. Une fonction f(x, y) est définie par « si y vaut 0, renvoyer x ; sinon, renvoyer f(y, x mod y) ». Quand on appelle f(84, 36), quelle est la valeur renvoyée, et combien de fois f est-elle appelée, premier appel compris ?
  4. Une fonction fib(n) qui calcule les nombres de Fibonacci est définie par récursion : « si n vaut 1 ou moins, renvoyer n ; sinon, renvoyer fib(n−1) + fib(n−2) ». Quand on appelle fib(5), combien de fois fib est-elle appelée, premier appel compris ?
  5. On paie 8 yens avec des pièces de 1 yen, 4 yens et 6 yens. Quelle affirmation relie correctement le nombre de pièces choisi par un algorithme glouton, qui utilise d'abord autant que possible la plus grosse pièce, et le nombre minimal de pièces ?