Quelle est l'implémentation de Dijkstra la plus rapide que vous connaissez (en C ++)?

Je l'ai fait récemment joindre la 3ème version de Dijkstra algorithme de plus court chemin de la source unique dans mon projet.

Je me rends compte qu'il existe de nombreuses implémentations différentes qui varient fortement dans la performance et aussi à faire varier la qualité du résultat dans les grands graphes. Avec mon jeu de données (> 100.000 sommets) le moteur d'exécution varie de 20 minutes à quelques secondes. Th chemins les plus courts aussi varier de 1 à 2%.

Qui est la meilleure application que vous connaissez?

EDIT:
Mes Données est un réseau hydraulique, avec 1 à 5 sommets par nœud. Son comparable à un plan de rue. J'ai fait quelques modifications à un déjà permis une accélération de l'algorithme à l'aide d'une liste triée de tous les autres nœuds) et maintenant de trouver les mêmes résultats en une fraction de temps. J'ai cherché quelque chose pour un certain temps. Je me demande si une telle application existe déjà.

Je ne peux pas expliquer les légères différences dans les résultats. Je sais que Dijkstra n'est pas heuristique, mais toutes les implémentations semblent corrects. La plus rapide des solutions ont les résultats les plus courts chemins. J'utilise la double précision de mathématiques exclusivement.

EDIT 2:
J'ai trouvé que les différences dans le chemin trouvé, en effet, sont de ma faute. J'avais inséré un traitement spécial à certains sommets (valable uniquement dans un seul sens) et j'ai oublié que dans les autres de la mise en œuvre.

MAIS je suis encore plus surpris que Dijkstra peut être accéléré de manière spectaculaire par la modification suivante:
En général, un algorithme de Dijkstra contient une boucle comme:

MyListType toDoList; //List sorted by smallest distance 
InsertAllNodes(toDoList);
while(! toDoList.empty())
{
    MyNodeType *node = *toDoList.first();
    toDoList.erase(toDoList.first());
    ...
}

Si vous changer un peu, et il fonctionne de la même façon, mais se comporte mieux:

MyListType toDoList; //List sorted by smallest distance 
toDoList.insert(startNode);
while(! toDoList.empty())
{
    MyNodeType *node = *toDoList.first();
    toDoList.erase(toDoList.first());
    for(MyNeigborType *x = node.Neigbors; x != NULL; x++)
    {
        ...
        toDoList.insert(x->Node);
    }
}

Il semble, que cette modification réduit le moment de l'exécution par un ordre pas de grandeur, mais un ordre de l'exposant. Il réduit mon runtime formulaire de 30 Secondes à moins de 2. Je ne trouve pas cette modification dans toute la littérature. Il est aussi très clair que la raison se trouve dans la liste triée. insérer/effacer effectue bien pire avec 100.000 éléments avec une main pleine de.

RÉPONSE:

Après beaucoup de recherches sur google, j'ai trouvé moi-même. La réponse est clairement:
boost graph lib. Incroyable - je n'avais pas trouvé ça pendant un bon moment. Si tu penses qu'il n'y a pas de variation de la performance entre les implémentations de Dijkstra, voir wikipedia.

source d'informationauteur RED SOFT ADAIR | 2009-06-02