Por que o algoritmo de Dijkstra usa tecla de diminuição?

O algoritmo de Dijkstra que me foi ensinado foi o seguinte

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)

Mas tenho feito algumas leituras a respeito do algoritmo, e muitas versões que vejo usam a tecla de diminuição em vez de inserir.

Por que isso acontece e quais são as diferenças entre as duas abordagens?

A razão para usar a tecla de diminuição em vez de reinserir nós é manter pequeno o número de nós na fila de prioridade, mantendo assim o número total de desenfileiramentos da fila de prioridade pequeno e o custo de cada equilíbrio de fila de prioridade baixo.

Em uma implementação do algoritmo de Dijkstra que reinsere nós na fila de prioridade com suas novas prioridades, um nó é adicionado à fila de prioridade para cada uma das m arestas do gráfico. Isso significa que há operações de enfileiramento e operações de desenfileiramento na fila de prioridade, dando um tempo de execução total de O (m T _e + m T _d ), onde T _e é o tempo necessário para enfileirar na fila de prioridade e T _d é o tempo necessário para retirar da fila de prioridade.

Em uma implementação do algoritmo de Dijkstra que suporta chave de diminuição, a fila de prioridade que contém os nós começa com n nós e em cada etapa do algoritmo remove um nó. Isso significa que o número total de retiradas da fila de heap é n. Cada nó terá a tecla de diminuição chamada potencialmente uma vez para cada aresta que conduz a ele, então o número total de teclas de diminuição feitas é no máximo m. Isso dá um tempo de execução de (n T _e + n T _d + m T _k ), onde T _k é o tempo necessário para chamar a tecla de diminuição.

Então, que efeito isso tem no tempo de execução? Isso depende de qual fila de prioridade você usa. Aqui está uma tabela rápida que mostra as diferentes filas de prioridade e os tempos de execução gerais das diferentes implementações do algoritmo 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)

Como você pode ver, com a maioria dos tipos de filas de prioridade, realmente não há diferença no tempo de execução assintótico, e a versão de diminuição da chave provavelmente não se sairá muito melhor. No entanto, se você usar uma implementação de heap de Fibonacci da fila de prioridade, então, de fato, o algoritmo de Dijkstra será assintoticamente mais eficiente ao usar a tecla de diminuição.

Resumindo, usar a tecla de diminuição, mais uma fila de boa prioridade, pode diminuir o tempo de execução assintótico de Dijkstra além do que é possível se você continuar fazendo enfileiramentos e desfileiramentos.

Além desse ponto, alguns algoritmos mais avançados, como o algoritmo de caminhos mais curtos de Gabow, usam o algoritmo de Dijkstra como uma sub-rotina e dependem fortemente da implementação de teclas de diminuição. Eles usam o fato de que, se você souber o intervalo de distâncias válidas com antecedência, poderá construir uma fila de prioridades supereficiente com base nesse fato.

Espero que isto ajude!

Em 2007, houve um artigo que estudou as diferenças no tempo de execução entre o uso da versão de diminuição da chave e a versão de inserção. Consulte http://www.cs.utexas.edu/users/shaikat/papers/TR-07-54.pdf

Sua conclusão básica foi não usar a tecla de diminuição para a maioria dos gráficos. Especialmente para gráficos esparsos, a chave de não diminuição é significativamente mais rápida do que a versão de chave de diminuição. Veja o jornal para mais detalhes.

Existem duas maneiras de implementar Dijkstra: uma usa um heap que suporta a tecla de diminuição e outra um heap que não suporta isso.

Ambos são válidos em geral, mas o último geralmente é o preferido. A seguir, usarei 'm' para denotar o número de arestas e 'n' para denotar o número de vértices de nosso gráfico:

Se você deseja a melhor complexidade de pior caso possível, você escolheria um heap de Fibonacci que suporte tecla de diminuição: você obterá um bom O (m + nlogn).

Se você se preocupa com o caso médio, pode usar um heap Binário também: você obterá O (m + nlog (m / n) logn). A prova está aqui , páginas 99/100. Se o gráfico for denso (m >> n), tanto este quanto o anterior tendem a O (m).

Se você quiser saber o que acontece se você executá-los em gráficos reais, pode verificar este artigo, como sugeriu Mark Meketon em sua resposta.

O que os resultados dos experimentos mostrarão é que um heap "mais simples" fornecerá os melhores resultados na maioria dos casos.

Na verdade, entre as implementações que usam uma tecla de diminuição, Dijkstra tem um desempenho melhor ao usar um heap Binário simples ou um heap de Emparelhamento do que quando usa um heap de Fibonacci. Isso ocorre porque os heaps de Fibonacci envolvem fatores constantes maiores e o número real de operações de redução de teclas tende a ser muito menor do que o que o pior caso prevê.

Por motivos semelhantes, um heap que não precisa oferecer suporte a uma operação de diminuição de tecla tem fatores ainda menos constantes e, na verdade, tem melhor desempenho. Especialmente se o gráfico for esparso.