Algoritmos de Caminho Mais Curto

Algoritmos de caminho mais curto calculam rotas de peso mínimo entre vértices em um grafo ponderado, com diferentes algoritmos adequados para pesos não negativos, pesos negativos e consultas de todos os pares versus fonte única.

Definition

Um caminho mais curto entre dois vértices em um grafo ponderado é um caminho cujo peso total das arestas é mínimo; algoritmos de caminho mais curto calculam tais caminhos e suas distâncias, seja de uma fonte para todos os vértices ou entre todos os pares de vértices.

Scope

Este tópico abrange caminhos mais curtos de fonte única (algoritmo de Dijkstra para pesos não negativos, Bellman-Ford para grafos com pesos negativos e para detecção de ciclos negativos), caminhos mais curtos de todos os pares (Floyd-Warshall, algoritmo de Johnson) e caminhos mais curtos em grafos acíclicos direcionados. Ele trata o princípio de relaxamento comum a esses métodos e o papel das filas de prioridade na implementação eficiente. Exclui caminhos mais curtos não ponderados obtidos por busca em largura, abordados em travessia de grafos.

Core questions

• Como o relaxamento de arestas progressivamente ajusta as estimativas de distância em direção às verdadeiras distâncias mais curtas?
• Por que o algoritmo de Dijkstra exige que os pesos das arestas sejam não negativos para estar correto?
• Como Bellman-Ford lida com pesos negativos e detecta ciclos negativos?
• Quando é mais eficiente calcular caminhos mais curtos de todos os pares do que repetir um método de fonte única?
• Como as escolhas da fila de prioridade afetam o tempo de execução do algoritmo de Dijkstra?

Key concepts

• relaxamento de aresta
• caminhos mais curtos de fonte única
• algoritmo de Dijkstra
• algoritmo de Bellman-Ford
• ciclos de peso negativo
• caminhos mais curtos de todos os pares
• algoritmo de Floyd-Warshall
• implementação de fila de prioridade

Key theories

Relaxamento de arestas e seleção gulosa

Algoritmos de caminho mais curto relaxam repetidamente as arestas, substituindo uma estimativa de distância quando uma rota mais curta é encontrada; o algoritmo de Dijkstra finaliza gulosamente o vértice não resolvido mais próximo, o que está correto precisamente porque os pesos das arestas são não negativos.

Programação dinâmica para caminhos de todos os pares

O algoritmo de Floyd-Warshall calcula caminhos mais curtos de todos os pares por um programa dinâmico sobre vértices intermediários, executando em tempo cúbico e lidando naturalmente com pesos de arestas negativos (sem ciclos negativos).

Clinical relevance

Algoritmos de caminho mais curto impulsionam serviços de navegação e mapeamento, protocolos de roteamento de pacotes em redes, planejamento de rotas em logística e qualquer sistema que encontre caminhos de menor custo através de uma rede ponderada, incluindo busca de caminho em jogos e cálculos de distância de recursos em análise espacial.

History

Dijkstra publicou seu algoritmo de caminho mais curto de fonte única em 1959. O algoritmo de Bellman-Ford, que lida com pesos negativos, surgiu do trabalho de Bellman, Ford e Moore no final da década de 1950. O algoritmo de Floyd de 1962, baseado no método de fechamento transitivo de Warshall, forneceu uma solução compacta para todos os pares que permanece um padrão.

Key figures

• Edsger W. Dijkstra
• Richard Bellman
• Lester Ford
• Robert W. Floyd

Seminal works

• dijkstra1959
• floyd1962
• cormen2009

Frequently asked questions

Por que o algoritmo de Dijkstra não consegue lidar com pesos de arestas negativos?

O algoritmo de Dijkstra finaliza o vértice não resolvido mais próximo e nunca o revisita, assumindo que nenhum caminho posterior pode ser mais curto. Uma aresta negativa poderia criar um caminho mais curto depois que um vértice é resolvido, quebrando a suposição. Bellman-Ford, que relaxa todas as arestas repetidamente, é usado em vez disso.

Quando devo usar um algoritmo de todos os pares em vez de executar Dijkstra a partir de cada vértice?

Para grafos densos ou quando muitas ou todas as distâncias de origem-destino são necessárias, a simples computação de tempo cúbico de todos os pares de Floyd-Warshall é frequentemente preferível. Para grafos esparsos, executar Dijkstra (ou o algoritmo de Johnson para pesos negativos) de cada fonte pode ser assintoticamente mais rápido.