01-04-2008, 01:35 PM
Oui, j'utilise Dijkstra, mais je n'ai pas trouvé d'implémentation qui me plaisait, alors je l'ai programmé à ma sauce à moi. Déjà, je ne prends pas les sommets un par un, mais comme il y a beaucoup de sommets de même poids, je prends tous les sommets de poids minimum en même temps. Et je n'ai pas de recherche de minimum, j'utilise un tableau et une matrice pour ranger les sommets à prendre au fur et à mesure. Et puis j'en profite pour stocker le "parent" de chaque case, ainsi on stocke le plus court chemin à partir de l'origine vers n'importe quelle case sans avoir à relancer de fonction... Et pour tout ça, je fais qu'une seule boucle, donc c'est assez optimisé quand même...