J'ai récemment joint la 3ème version de l'algorithme de Dijkstra pour le plus court chemin de source unique dans mon projet.Quelle est l'implémentation de Dijkstra la plus rapide que vous connaissez (en C++)?
Je me rends compte qu'il existe de nombreuses implémentations différentes qui varient fortement dans les performances et qui varient également dans la qualité du résultat dans les grands graphiques. Avec mon jeu de données (> 100.000 sommets), le temps d'exécution varie de 20 minutes à quelques secondes. Les chemins les plus courts varient également de 1-2%.
Quelle est la meilleure implémentation que vous connaissez?
EDIT: Mes données est un réseau hydraulique, avec 1 à 5 sommets par nœud. C'est comparable à une carte de rue. J'ai fait quelques modifications à un algorithme déjà accéléré (en utilisant une liste triée pour tous les nœuds restants) et maintenant trouver les mêmes résultats dans une fraction de temps. J'ai cherché une telle chose pendant un bon moment. Je me demande si une telle mise en œuvre 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 correctes. Les solutions les plus rapides ont les résultats avec des chemins plus courts. J'utilise exclusivement les mathématiques à double précision. J'ai découvert que les différences dans le chemin trouvé sont en fait de ma faute. J'avais inséré une manipulation spéciale pour certains sommets (valable uniquement dans une direction) et oublié dans l'autre implémentation.
MAIS im encore plus surpris que Dijkstra peut être considérablement accéléré par le changement suivant: 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 changez un peu, il fonctionne de la même, mais fonctionne 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 temps d'exécution d'un ordre de grandeur non, mais un ordre d'exposant. Il a réduit ma forme d'exécution 30 secondes à moins de 2. Je ne trouve pas cette modification dans la littérature. Il est également très clair que la raison réside dans la liste triée. insérer/effacer effectue bien pire avec 100.000 éléments qu'avec une main pleine de.
RÉPONSE:
Après beaucoup de googler je l'ai trouvé moi-même. La réponse est clairement: boost graph lib. Incroyable - je n'avais pas trouvé ça depuis longtemps. Si vous pensez qu'il n'y a pas de variation de performance entre les implémentations de Dijkstra, voyez wikipedia.
Un de mes amis peut implémenter Dijkstra en C++ en environ 3 minutes. Je n'ai pas entendu parler d'implémentations plus rapides. – jbasko
Je suggérerais que vous souhaitiez vérifier ces implémentations ... si elles sont correctes, elles devraient toutes retourner le même chemin le plus court ... L'algorithme de Dijkstra n'est pas heuristique ... – jerryjvl
Les différences dans les chemins les plus courts peuvent être le résultat de en utilisant des maths à double précision, à cause des erreurs d'arrondi lors de la sommation de longues séquences de doubles. Un ordre de sommation différent peut produire différentes erreurs. Pouvez-vous tester vos implémentations sur des entiers? –