File de priorité
La bibliothèque Python heapq permet de réaliser facilement une file de priorité. Voici un lien vers la doc officielle.
Avec ce module, vous pouvez créer une file de priorité simplement comme suit :
|
1 2 |
import heapq priorityQueue = [] |
Les éléments sont ajoutés à la file via la fonction heappush, et retirés via la fonction heappop. Cette dernière fonction renvoie (en le retirant de la structure) l’élément minimum. Pour associer une clé aux éléments de la liste, il suffit d’insérer une paire dans la file de priorité, comme suit :
|
1 2 3 4 5 6 7 8 |
import heapq priorityQueue = [] heapq.heappush(priorityQueue, (18, "a")) heapq.heappush(priorityQueue, (15, "b")) heapq.heappush(priorityQueue, (16, "c")) minKey, minElement = heapq.heappop(priorityQueue) print(minKey, minElement) # 15 b print(priorityQueue) # [(16, 'c'), (18, 'a')] |
Dijkstra
Implémenter l’algorithme de Dijkstra, ainsi que le routage permettant de reconstruire un plus court chemin d’un point A à un point B.
Quoi faire ensuite ?
Les résultats obtenus en suivant ce TP seront présentés lors de l’entretien de la séance 6.
Ramassez un morceau de fromage dans un labyrinthe pondéré (ou non) en utilisant un chemin le plus court.
Tracez l’influence de la taille du labyrinthe (ou d’un autre paramètre plus intéressant) sur la longueur du chemin le plus court.
Allez plus loin ! Quelques pistes : comparaisons avec Floyd-Warshall, lien mesures/complexité, meilleure implémentation de l’algorithme, etc.