Pourquoi l'algorithme de Dijkstra utilise-t-il la touche décroissante?

L'algorithme de Dijkstra m'a été appris 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 la touche de diminution plutôt que l'insertion.

Pourquoi cela et quelles sont les différences entre les deux approches?

La raison de l'utilisation de la touche de diminution plutôt que de la réinsertion de nœuds est de maintenir le nombre de nœuds dans la file d'attente prioritaire faible, ce qui réduit le nombre total de files d'attente prioritaires et le coût de chaque solde de file d'attente prioritaire faible.

Dans une implémentation de l'algorithme de Dijkstra qui réinsère les nœuds dans la file d'attente prioritaire avec leurs nouvelles priorités, un nœud est ajouté à la file d'attente prioritaire pour chacun des m arêtes du graphique. Cela signifie qu'il y a m opérations de mise en file d'attente et m opérations de mise en file d'attente sur la file d'attente prioritaire, ce qui donne un temps d'exécution total de O (m T _e + m T _d ), où T _e est le temps nécessaire pour mettre en file d'attente la file d'attente prioritaire et T _d est le temps nécessaire pour se retirer de la file d'attente prioritaire.

Dans une implémentation de l'algorithme de Dijkstra qui prend en charge la clé de décroissance, la file d'attente 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 files d'attente du tas est n. Chaque nœud aura une touche de diminution appelée potentiellement une fois pour chaque arête qui y mène, de sorte que le nombre total de touches de diminution effectuées est d'au plus m. Cela donne un temps d'exécution de (n T _e + n T _d + m T _k ), où T _k est le temps nécessaire pour appeler la touche de diminution.

Alors, quel effet cela a-t-il sur l'exécution? Cela dépend de la file d'attente prioritaire que vous utilisez. Voici un tableau rapide qui montre les différentes files d'attente de priorité et les temps d'exécution globaux des différentes implémentations d'algorithme 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 voir, avec la plupart des types de files d'attente prioritaires, il n'y a vraiment pas de différence dans l'exécution asymptotique, et la version à clé réduite ne fera probablement pas beaucoup mieux. Cependant, si vous utilisez une implémentation de tas de Fibonacci de la file d'attente prioritaire, alors en effet l'algorithme de Dijkstra sera asymptotiquement plus efficace lors de l'utilisation de la touche de diminution.

En bref, l'utilisation de la touche de diminution, plus une bonne file d'attente prioritaire, peut faire tomber le runtime asymptotique de Dijkstra au-delà de ce qui est possible si vous continuez à faire des files d'attente et des retraits.

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 s'appuient fortement sur l'implémentation de la clé décroissante. Ils utilisent le fait que si vous connaissez à l'avance la plage de distances valides, vous pouvez créer une file d'attente prioritaire super efficace sur cette base.

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 à décroissance et la version à insérer. Voir http://www.cs.utexas.edu/users/shaikat/papers/TR-07-54.pdf

Leur conclusion fondamentale était de ne pas utiliser la touche de diminution pour la plupart des graphiques. Surtout pour les graphiques clairsemés, la touche sans diminution est nettement plus rapide que la version avec touche de diminution. Voir l'article pour plus de détails.

Il existe deux façons d'implémenter Dijkstra: l'une utilise un tas qui prend en charge la touche de diminution et l'autre un tas qui ne prend pas en charge cela.

Ils sont tous deux valables en général, mais ce dernier est généralement préféré. Dans ce qui suit, j'utiliserai 'm' pour désigner le nombre d'arêtes et 'n' pour désigner le nombre de sommets de notre graphe:

Si vous voulez la meilleure complexité possible dans le pire des cas, vous opteriez pour un tas de Fibonacci qui prend en charge la touche de diminution: vous obtiendrez un joli O (m + nlogn).

Si vous vous souciez du cas moyen, vous pouvez également utiliser un tas binaire: vous obtiendrez O (m + nlog (m / n) logn). La preuve en est ici , pages 99/100. Si le graphique est dense (m >> n), celui-ci et le précédent tendent tous deux vers O (m).

Si vous voulez savoir ce qui se passe si vous les exécutez sur de vrais graphiques, vous pouvez consulter cet article, comme Mark Meketon l'a suggéré dans sa réponse.

Ce que les résultats des expériences montreront, c'est qu'un tas "plus simple" donnera les meilleurs résultats dans la plupart des cas.

En fait, parmi les implémentations qui utilisent une clé de décroissance, Dijkstra fonctionne mieux lorsqu'il utilise un simple tas binaire ou un tas d'appariement que lorsqu'il utilise un tas de Fibonacci. Cela est dû au fait que les tas de Fibonacci impliquent des facteurs constants plus importants et que le nombre réel d'opérations de diminution de la touche a tendance à être beaucoup plus petit que ce que le pire des cas prédit.

Pour des raisons similaires, un tas qui n'a pas à prendre en charge une opération de diminution de la clé, a des facteurs encore moins constants et fonctionne mieux. Surtout si le graphique est clairsemé.