Discussion :

[Gryzzly]

Bonjour,

je voudrais savoir ce qu'est une file de priorité et à quoi cela sert 'il ?

Merci

[FrancisSourd]

Wikipédia!
http://fr.wikipedia.org/wiki/File_%C3%A0_priorit%C3%A9s

[Gryzzly]

Wikipédia!
http://fr.wikipedia.org/wiki/File_%C3%A0_priorit%C3%A9s

Merci.

J'aurais une question car je dois coder l'algo de Dijkstra en utilisant une file de priorité.
En utilisant une file de priorité,avec quelle structure (matrice ou liste) ,obtient 'on la meilleure complexité?

[Sib]

Pour l'algorithme de Dijkstra, on utilise, en tant que file de priorité, un tas de Fibonacci (cf "Introduction à l'Algorithmique" de Thomas H. Cormen)
Avec une telle structure, l'algorithme de Dijkstra s'exécute en temps O(m + nlogn), où m est le nombre d'arcs du graphe, et n le nombre de noeuds du graphe..