Discussion :

[Aspharr]

Bonjour,

Je travaille sur l'algorithme de Dijkstra (si vous ne connaissez pas voici le lien
http://fr.wikipedia.org/wiki/Algorithme_de_Dijkstra).

J'aimerais simplement savoir comment trouver la complexité,bien qu'elle soit ecrite je ne sais pas comment a partir des données de depart on peut la trouver.

Ou plutôt comment savoir qu'il s'agit d'une complexité quasi linéaire.


J'espere que vous coprenez ma requete et merci pour laide apportée.

[FrancisSourd]

Regarde la section 7.2.6 dans cet ouvrage en ligne
http://www-igm.univ-mlv.fr/~berstel/.../Elements.html

[FrancisSourd]

Par complexité quasi linéaire, entends-tu bien O((m+n)log n)?

Souvent, on dit que log n est borné en pratique en raison de la taille de mémoire des ordinateurs, d'ooù ce terme de quasi-linéaire.