Seance 6 Dijkstra 2 Intuition

Séance 6 (2/2) — Algorithme de Dijkstra : intuition et pseudo-code¶

VERSION ELEVE

Pour aller plus loin : la preuve formelle de terminaison/correction et l'analyse de complexité (anciennement dans cette activité) sont désormais dans une annexe optionnelle (Annexe_Dijkstra_Preuve_Complexite.ipynb). L'implémentation en Python se fait en Séance 7 (Seance_7_Dijkstra_Implementation.ipynb).

Conditions de réalisation :¶

• Un ordinateur par élève équipé pour lire une video avec casque ou oreillette, et Jupyter Notebook.
• Seul le travail à faire "Taf1" sera réalisé en binôme. Les autres travaux le seront en individuel.
• Une version papier de ce notebook pour les travaux à faire "en débranché".
• A partir du Taf6, le travail est à faire directement sur ce notebook.

1- Présentation¶

Lors des cours et activités précédentes, vous avez étudié le fonctionnement, l'usage et les limites de plusieurs algorithmes constituant une base de travail pour résoudre des problèmes de tri et de recherche. Certains problèmes consistent à chercher entre deux points donnés le parcours qui a une "longueur" (durée, coût, distance) minimum. Ces problèmes se ramènent à la recherche d'une chaîne ou d'un chemin de plus faible pondération entre deux sommets d'un graphe pondéré (les pondérations des arêtes étant toutes positives). On parlera de plus courte distance (ou de plus court chemin) en interprétant les pondérations comme des distances entre les sommets. Classifions maintenant ces problème. On peut en distinguer trois types : 1- plus court chemin entre deux sommets donnés; 2- plus courts chemins d’origine fixée mais vers n’importe quelle extrémité ; 3- plus courts chemins de n’importe quelle origine vers n’importe quelle extrémité. Pour la 1ère catégorie, si le nombre de chemins possibles entre le point de départ et le point d'arrivée est faible, il suffira de calculer la longueur cumulée de chacun des chemins et de les comparer. Remarque: une telle méthode, exhaustive, devient rapidement couteuse en temps si le nombre de chemins possibles est grand, surtout pour les 2ème et 3ème catégorie.

Trouver les chemins issus d’un sommet : l’algorithme de Dijkstra¶

Parmi les nombreux algorithmes traitant de "chemin de valeur additive minimale", celui de Dijkstra repose sur le principe d’« exploration à partir du meilleur », c’est à dire du meilleur prédécesseur visité.

Description sommaire de l'algorithme de Dijkstra:¶

•- Initialisation:

• Associer à chaque sommet du graphe une distance infinie par rapport au sommet de départ, sauf pour le sommet de départ qui prend la valeur 0. •- Répèter de façon itérative les opérations suivantes jusqu'au dernier sommet du graphe à explorer :
• Sélectionner à chaque itération le sommet du graphe qui a la distance la plus petite, remarque: démarrer avec le sommet de départ.
• Pour chacun des voisins de ce sommet:
• Calculer la distance cumulée qui le sépare du départ en passant par ce sommet sélectionné.
• Si cette distance est plus petite qu'une valeur précédente mémorisée: garder cette dernière distance cumulée en mémoire ainsi que le sommet voisin sélectionné. •- Résultat:
• En refaisant le meilleur parcours mémorisé à l'envers à partir d'un sommet autre que celui de départ,on obtient le trajet entre ces deux sommets.
• Associée au trajet , on obtient la dernière plus courte distance cumulée du plus court chemin qui sépare le dernier sommet exploré du sommet de départ.

Travail à faire 1 (en binôme), Tableau des plus courts chemins¶

1- En exploitant la description sommaire de l'algorithme de Dijkstra ci-dessus et de la vidéo https://www.youtube.com/watch?v=rI-Rc7eF4iw, essayez de retrouver votre résultat intuitif du chemin le plus court entre les sommets A et G de la 1ère partie de cette évaluation et que que vous aviez confirmé avec la méthode "naïve", dite aussi "de force brute". Pour cela, vous pourrez compléter un tableau adapté à notre problème (un modèle, 1ère ligne complétée vous est proposé ci-dessous). 2- Existe t'il une variable contenant la distance cumulée de ce plus court chemin? Justifier.

2- Algorithme de Dijkstra en pseudo-code¶

Travail à faire 2, algorithme et variables¶

Ci-dessous, vous est proposé une écriture possible de l'algorithme de Dijkstra: 1- Dans cet algorithme, identifier la variable qui donnera le plus court chemin entre le sommet de départ et le dernier sommet visité du graphe lorsque le traitement sera terminé. 2- Dans cet algorithme, existe t'il une variable contenant la distance de ce plus court chemin? Justifier. 3- Catégorisation de l'algorithme de Dijkstra: répondre au QCM1 ci-dessous.

$QCM1:$ Dans l'écriture de l'algorithme de Dijkstra proposée ci-dessus, on peut remarquer que: $Rep1:$ La recherche, à chaque itération, du plus proche sommet voisin signifie que cet algorithme fait partie de la famille des 'algorithmes des k plus proches voisins'. $Rep2:$ La recherche d’une solution optimale à un moment donné sans retour en arrière, indique qu'il s'agit d'une forme d'algorithme 'glouton'. $Rep3:$ Le fait qu'à chaque itération, l'algorithme sélectionne 'le sommet non encore traité dont la distance à l'origine est minimale', c'est à dire le meilleur, est un élément clé pour montrer qu'il s'agit d'un algorithme glouton. $Rep4:$ La résolution des problèmes du "rendu de monnaie" et du "plus court chemin" peuvent être envisagées par des approches dites 'gloutonnes'