Algoritmo de Dijkstra
- Proposto por
- Edsger W. Dijkstra
- Ano
- 1956
- Tipo
- algorithm
- Família
- Graph Algorithms
Este texto é uma tradução automática e ainda não foi revisado. Ler o original em inglês
O que ele faz?
O Algoritmo de Dijkstra, introduzido por Edsger W. Dijkstra em 1956, é um dos algoritmos mais fundamentais da ciência da computação para resolver o problema do caminho mais curto de origem única.
Ele encontra o caminho mais curto de um vértice inicial para todos os outros vértices em um grafo ponderado com pesos de aresta não negativos.
A intuição por trás do método
O algoritmo mantém um conjunto de vértices cujas distâncias mais curtas da origem já são conhecidas e expande iterativamente este conjunto selecionando o vértice não processado mais próximo e atualizando as distâncias para seus vizinhos. A percepção chave é a propriedade gulosa: uma vez que um vértice é selecionado, sua distância da origem é final porque todos os pesos das arestas são não negativos, então qualquer caminho mais longo através de vértices não visitados não pode ser mais curto. Isso garante correção e otimalidade.
História
Edsger W. Dijkstra publicou seu algoritmo em 1959 em um artigo de três páginas que se tornaria um dos trabalhos mais citados em ciência da computação. O algoritmo surgiu do trabalho de Dijkstra no computador ARMAC em Amsterdã. Ao longo de décadas, inúmeras melhorias foram feitas, incluindo melhores estruturas de dados (heaps de Fibonacci alcançando complexidade O(E+VlogV)) e variantes bidirecionais. O algoritmo permanece central para protocolos de roteamento modernos como OSPF em redes.
Quando usar
Aplique o algoritmo de Dijkstra ao encontrar caminhos mais curtos em grafos com pesos de aresta não negativos. É ideal para sistemas de navegação, roteamento de rede e qualquer problema de grafo que exija caminhos ótimos. Use-o para caminhos mais curtos de origem única para todos os vértices. Para grafos com pesos negativos, use Bellman-Ford em vez disso. Para busca bidirecional ou orientação heurística, considere o algoritmo A*.
Limitações e considerações
- Não consegue lidar com grafos com pesos de aresta negativos
- Calcula caminhos mais curtos para todos os vértices, não apenas um destino (embora possa terminar mais cedo)
- Menos eficiente que A* quando informações heurísticas estão disponíveis
- Requer que todos os vértices sejam descobertos; ineficiente para conectividade muito esparsa
As condições da fonte não substituem a revisão científica independente nem a validação por um motor de análise.
Pontos fortes
- Simples de entender e implementar com claras garantias de correção
- Eficiente com estruturas de dados adequadas: O((V+E)logV) com heap binário, O(V²) com array
- Ótimo para grafos com pesos não negativos; prova a otimalidade dos caminhos calculados
- Funciona em grafos direcionados e não direcionados
- Fundação para inúmeras extensões e algoritmos relacionados
Aplicações
- Sistemas de GPS e navegação: encontrando rotas mais curtas para veículos e pedestres
- Protocolos de roteamento de rede: determinando caminhos ótimos para pacotes de dados em redes de computadores
- Redes sociais: encontrando caminhos de conexão mais curtos entre usuários ou influenciadores
- Desenvolvimento de jogos: pathfinding para inteligência artificial e movimento de personagens não jogáveis
- Planejamento de movimento de robôs: computando trajetórias ótimas para sistemas robóticos
- Telecomunicações: otimizando roteamento de chamadas e caminhos de propagação de sinal
Como funciona
Como funciona
Defina a distância da origem como zero e todas as outras distâncias como infinito. Marque todos os vértices como não visitados e crie uma fila de prioridade.
Selecione o vértice não visitado com distância mínima da origem usando a fila de prioridade.
Para cada vizinho do vértice selecionado, se o caminho através do vértice selecionado oferecer uma distância menor, atualize a distância do vizinho e adicione-o à fila de prioridade.
Erros comuns
- Usar o algoritmo em grafos com pesos negativos, resultando em caminhos mais curtos incorretos
- Implementação ineficiente com operação de extração-mínimo em tempo linear, levando a um desempenho ruim
- Falha ao atualizar corretamente as distâncias quando vizinhos são revisitados através de caminhos diferentes
Perguntas frequentes
Por que o algoritmo de Dijkstra falha em pesos negativos?
O algoritmo assume que, uma vez que um vértice é finalizado, nenhum caminho mais curto pode ser encontrado através de vértices não visitados. Com pesos negativos, um caminho mais longo pode melhorar posteriormente quando uma aresta negativa é usada, violando essa suposição.
Qual estrutura de dados deve ser usada para a fila de prioridade?
Heaps binários fornecem operações O(logV) tanto para inserção quanto para extração, resultando em complexidade total O((V+E)logV). Heaps de Fibonacci alcançam O(E+VlogV), mas têm grandes fatores constantes. Arrays funcionam bem para grafos pequenos.
Como o algoritmo de Dijkstra pode encontrar o caminho para um destino específico?
Termine o algoritmo assim que o vértice de destino for selecionado (sua distância for finalizada), evitando computação desnecessária. Alternativamente, reconstrua o caminho mantendo ponteiros pai durante a execução.
O algoritmo de Dijkstra pode ser usado em grafos não direcionados?
Sim, grafos não direcionados podem ser representados como grafos direcionados com arestas em ambas as direções para cada aresta não direcionada, cada uma com o mesmo peso. O algoritmo funciona identicamente na representação bidirecional.
Métodos relacionados
Fontes
Dijkstra, E. W. (1959). A note on two problems in connexion with graphs. Numerische Mathematik, 1(1), 269-271.
Abrir referência DOICopiado.Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press.
ISBN: 978-0-262-03384-8Copiado.