A* et Dijkstra sont quasiment identiques. La différence vient de l'heuristique : F = G + H
Pour A*, G est la distance entre le point courant et l'arrivée, H la distance entre le point courant et son parent.
Pour Dijkstra, G vaut toujours 0.

Les essais que j'ai fait montrent que Dijkstra trouve toujours le chemin le plus court contrairement à A*.
Par contre A* est plus rapide dans la majorité des cas puisque que son heuristique l'oriente vers l'arrivée tandis qu'avec Dijkstra chaque nœud est étudié.

J'ai finalement opté pour la fonction de tri de la STL. J'ai fais un "pseudo" tri par insertion mais ça n'était pas concluant.
Ça me convient pour le moment ; ça règle mais deux problèmes :
- je ne garde pas un pointeur comme référence, ni un size_t mais un iterator qui ne change pas après les tris successifs.
- le meilleur nœud est toujours situé en début de liste, ça évite une recherche coûteuse en temps.