Discussion :

[BigBother]

Bonjour a tous,
pour un projet universitaire j'ai besoin d'implementer l'algorithme de Dijkstra, et donc la file de priorité qui lui est associé.
J'ai décidé d'implementer la file dans un tableau puisque le nombre de sommet du graphe (et donc d'element dans la file) est fixe
Dijkstra demande d'implementer des fonction de mise a jours d'element déjà présent dans la file de priorité, ce qui implique de retrouver l'element en question au sein de la file. Je ne sais pas trop comment m'y prendre sans avoir a parcourir le tableau et de me retrouver avec une complexité O(n) pour chaque mise a jour, quelqu'un aurait une idée ?
(je précise que je code en C, je ne peut donc pas utiliser les structures deja implementé dans d'autres langages)
Merci

[dourouc05]

Tu as déjà regardé Wikipédia à ce sujet ? https://fr.wikipedia.org/wiki/File_de_priorit%C3%A9 L'idée de l'implémentation courante est d'éliminer la partie O(n) pour la lecture en remplaçant l'insertion et la suppression par du O(log n) par un tas (arbre "trié" implémenté dans un tableau).