Pourquoi l’algorithme de Dijkstra utilise-t-il la clé?

L’algorithme de Dijkstra m’a été enseigné comme suit

while pqueue is not empty: distance, node = pqueue.delete_min() if node has been visited: continue else: mark node as visited if node == target: break for each neighbor of node: pqueue.insert(distance + distance_to_neighbor, neighbor) 

Mais j’ai fait quelques lectures concernant l’algorithme, et beaucoup de versions que je vois utilisent des raccourcis plutôt que des insertions.

Pourquoi est-ce et quelles sont les différences entre les deux approches?

La raison de l’utilisation des raccourcis plutôt que de la réinsertion des noeuds est de limiter le nombre de noeuds dans la queue prioritaire, réduisant ainsi le nombre total de files d’attente de queue prioritaire et le coût de chaque solde de queue prioritaire.

Dans une implémentation de l’algorithme de Dijkstra qui réinsère des nœuds dans la queue prioritaire avec leurs nouvelles priorités, un nœud est ajouté à la queue prioritaire pour chacun des m bords du graphique. Cela signifie qu’il y a m opérations de mise en queue et m opérations de dé-queue sur la queue prioritaire, ce qui donne un temps d’exécution total de O (m T e + m T d ), T e étant le temps nécessaire pour mettre en queue le temps nécessaire pour retirer de la queue de la queue prioritaire.

Dans une implémentation de l’algorithme de Dijkstra qui prend en charge la clé décroissante, la queue prioritaire contenant les nœuds commence par n nœuds et à chaque étape de l’algorithme supprime un nœud. Cela signifie que le nombre total de désemstackments de tas est n. Chaque nœud aura potentiellement une touche de raccourci une fois pour chaque arête qui le mène, de sorte que le nombre total de raccourcis effectués est au maximum m. Cela donne un temps d’exécution de (n T e + n T d + m T k ), où T k est le temps requirejs pour appeler la clé de diminution.

Alors, quel effet cela a-t-il sur le runtime? Cela dépend de la queue prioritaire que vous utilisez. Voici un tableau rapide qui montre les différentes files d’attente prioritaires et les temps d’exécution globaux des différentes implémentations d’algorithmes de Dijkstra:

 Queue | T_e | T_d | T_k | w/o Dec-Key | w/Dec-Key ---------------+--------+--------+--------+-------------+--------------- Binary Heap |O(log N)|O(log N)|O(log N)| O(M log N) | O(M log N) Binomial Heap |O(log N)|O(log N)|O(log N)| O(M log N) | O(M log N) Fibonacci Heap | O(1) |O(log N)| O(1) | O(M log N) | O(M + N log N) 

Comme vous pouvez le constater, avec la plupart des files d’attente de priorité, il n’y a pas vraiment de différence dans l’exécution asymptotique, et la version avec touches réduites ne fera probablement pas beaucoup mieux. Cependant, si vous utilisez une implémentation de tas Fibonacci de la queue prioritaire, l’algorithme de Dijkstra sera en effet asymptotiquement plus efficace lors de l’utilisation de la clé de réduction.

En bref, l’utilisation de diminutif, plus une bonne queue prioritaire, peut supprimer le runtime asymptotique de Dijkstra au-delà de ce qui est possible si vous continuez à faire des mises en queue et des désenregistrements.

Outre ce point, certains algorithmes plus avancés, tels que l’algorithme des chemins les plus courts de Gabow, utilisent l’algorithme de Dijkstra comme sous-programme et se basent largement sur l’implémentation par clé réduite. Ils utilisent le fait que si vous connaissez la gamme des distances valides à l’avance, vous pouvez créer une queue prioritaire très efficace en fonction de ce fait.

J’espère que cela t’aides!

En 2007, un article a étudié les différences de temps d’exécution entre l’utilisation de la version à clé réduite et la version d’insertion. Voir http://www.cs.utexas.edu/users/shaikat/papers/TR-07-54.pdf

Leur conclusion fondamentale était de ne pas utiliser la touche de réduction pour la plupart des graphiques. En particulier pour les graphiques fragmentés, la clé de non-diminution est nettement plus rapide que la version à clé réduite. Voir le papier pour plus de détails.