O Algoritmo de Dijkstra é um algoritmo ganancioso ou um algoritmo de programação dinâmico?

Um ponto subtil está a ser perdido em algumas respostas aqui (incluindo a resposta de topo neste momento, Nathan Pinsker's answer to Is Dijkstra's Algorithm a greedy algorithm or a dynamic programming algorithm?), por isso preciso de intervir pois é parcialmente errado e bastante enganador.

Problemas têm estrutura que exploramos para desenhar algoritmos para eles. O problema do caminho mais curto não é um "problema DP". É um problema que pode usar técnicas como a programação dinâmica para resolver. Este é um erro comum que as pessoas cometem; elas falam de problemas com respeito aos algoritmos ao invés da forma correta (algoritmos com respeito aos problemas). Eu acho que muita da confusão aqui é mais pedagógica do que científica; como você foi introduzido ao algoritmo. Eu realmente não conheço nenhum texto de referência padrão em áreas que vão desde Optimização Combinatória até Análise de Algoritmos que se refeririam ao algoritmo como um algoritmo dinâmico de programação (como não é). Por exemplo, o texto amplamente utilizado Algoritmo de Design por Kleinberg e Tardos certamente o descreve como um algoritmo ganancioso:

Source: https://www.cs.princeton.edu/courses/archive/spring13/cos423/lectures/04GreedyAlgorithmsII-2x2.pdf

P>Não mencionar, Introduction to Algorithms por Cormen et al. muito definitivamente o considera um algoritmo ganancioso.

Source: Introduction to Algorithms

O algoritmo de Dijkstra normalmente emprega uma fila de prioridade, você não poderia conseguir isso em um cenário onde você precisaria exclusivamente de programação dinâmica.

Tipicamente é considerado um algoritmo ganancioso, uma vez que ele fundamentalmente usa a propriedade de escolha gananciosa para obter o ótimo. Mas, pode-se implementar o algoritmo de Dijkstra como um algoritmo de programação dinâmica. É importante entender que estas duas categorias não são desunidas, o algoritmo tem propriedades que se poderia debater sobre isso. Normalmente quando as pessoas discutem algoritmos de programação dinâmica, eles falam em derivar uma relação de recorrência e preencher uma tabela para obter o valor ótimo, então (às vezes) aplicando backtracing para obter a solução real. Normalmente é a isso que as pessoas se referem como a abordagem de programação dinâmica porque utiliza o princípio da otimização (ver equação de Bellman - Wikipedia). O valor do óptimo é garantido através do princípio da optimalidade. Você pode fazer isso de uma maneira similar ao algoritmo de Dijkstra, mas a maneira como a maioria implementa Dijkstra não se encaixa nisso porque não precisamos preencher a tabela inteira. Nós sabemos que o problema do caminho mais curto satisfaz a propriedade da escolha gananciosa (se você quer cavar mais fundo, vá olhar para matroids gananciosos), por que trazer à tona as ferramentas mais fortes?

Para estudantes, eu normalmente o chamo de um algoritmo ganancioso porque ele se encaixa em tudo o que faz um algoritmo ganancioso. Você sempre usa o ótimo local para construir sua solução. Às vezes é útil apontar a abordagem de programação dinâmica que se pode usar para também escrever o algoritmo do Dijkstra, mas então o algoritmo do Dijkstra pode ser derivado de tantas maneiras diferentes (inclusive através de programação linear) que ele se torna um pouco solto demais para estudantes iniciantes e nós normalmente queremos mostrar as abordagens mais eficientes. O melhor é mantê-lo simples. Acho que só confunde os alunos ao chamá-lo de programação dinâmica, apesar de termos melhores rótulos para ele. Mas, devo enfatizar que você pode escrever o algoritmo do Dijkstra como um algoritmo de programação dinâmica apropriado, mas esta abordagem não é tão eficiente quanto o algoritmo ganancioso que normalmente discutimos (e nos referimos a estes dias).

A forma como as pessoas descrevem os algoritmos pode se tornar muito mais simples e refinada com o tempo. Quero dizer, se você pegar a abordagem que normalmente ensinamos onde você tem um array que armazena as distâncias que você atualiza, isto não é um algoritmo DP porque você constrói a solução conforme você vai (você sempre escolhe o mínimo para ser o próximo vértice enquanto você explora o gráfico), você não encontra o ótimo e depois retrocede (que é o que um algoritmo DP faz). Se você apenas diz "oh ele usa memorização" para afirmar que é um algoritmo DP, muitos algoritmos podem ser chamados de algoritmos DP, o que não é nada útil. As características fundamentais e típicas de um algoritmo DP são utilizar o princípio da optimização para calcular o valor óptimo e depois construir a solução através da travessia de sub-soluções óptimas. Eu acho que não é útil chamar-lhe um algoritmo DP de uma forma mais geral, uma vez que a forma como normalmente o ensinamos é construindo a solução à medida que se vai com zero de retrocesso. Porque manter todos os passos extras quando você tem a propriedade de escolha gananciosa à sua disposição?

O problema do caminho mais curto é muito interessante porque tantas abordagens funcionam para este problema que se sobrepõem.

Em resumo: É um algoritmo ganancioso, mas pode ser escrito como um algoritmo dinâmico de programação (mas isto não é tão eficiente em termos de espaço). Como descrito por especialistas em nossa área de origem acima, ele não se encaixa no processo de um algoritmo DP (como você usaria o princípio da otimização).