Please enable JavaScript.
Coggle requires JavaScript to display documents.
Dijkstra e algoritmos de caminho minímo - Coggle Diagram
Dijkstra e algoritmos de caminho minímo
Dijkstra
Estratégia: algoritmo guloso
Decisões são locais
Escolhe sempre o próximo vértice com menor distância conhecida
Não revisita vértices já processados
Não aceita pesos negativos
Aplicações comuns
GPS e mapas
Robôs autônomos
Planejamento de caminhos em jogos
Redes de computadores (protocolos de roteamento)
Complexidade
Matriz de adjacência: Θ(|V|²)
Floyd-Warshall
Aceita pesos negativos
Complexidade
Tempo: Θ(|V|³)
Espaço: Θ(|V|²),
Estratégia: Programação dinâmica
Usa subproblemas menores para construir a solução final
Considera todos os possíveis caminhos intermediários
Atualiza iterativamente as distâncias entre pares de vértices
Baseado em Warshall
Generaliza o algoritmo de Warshall (fecho transitivo)
Usa matriz D[i][j] representando a menor distância de i até j
Bellman-Ford
Aceita pesos negativos
Detecta ciclos negativos
Se for, há um ciclo de custo negativo acessível a partir da fonte
Após |V| - 1 iterações, verifica se ainda é possível relaxar alguma aresta
Pode ser usado para validar grafos em sistemas financeiros, por exemplo
Complexidade
Tempo: Θ(|V||E|)
Espaço: Θ(|V|)
Funcionamento por iterações
Inicializa distâncias (fonte = 0, outros = ∞)
Estratégia: Programação dinâmica
Relaxa todas as arestas repetidamente para atualizar as melhores distâncias
Armazena os menores custos intermediários até convergir
Baseia-se na ideia de que o menor caminho entre dois vértices usa no máximo |V| - 1 arestas
Algoritmos de caminho minímo
Objetivo
Minimizar custo/distancia/tempo
Otimizar rotas entre vértices
Suportar diferentes estruturas de grafo
Ponderado
Direcionado
Tipos de problema
Caminho mínimo de uma única fonte(sigle-source)
Caminho mínimo entre todos os pares(all-pairs)
Caminho com possibilidades de pesos negativos
Detectção de ciclos negativos
Características dos grafos
Grafo direcionado ou não-direcionado
Pesos positivos ou negativos
Densos ou esparsos
Presença ou ausência de ciclos
Aplicações
Planejamento de rotas em mapas
Roteamento de pacotes
Jogos (pathfinding em IA)
Robótica
Otimização de circuitos ou redes elétricas