Please enable JavaScript.
Coggle requires JavaScript to display documents.
Algoritmos de Caminho Mínimo - Coggle Diagram
Algoritmos de Caminho Mínimo
Algoritmo de Floyd
Funcionamento
Atualiza iterativamente considerando vértices intermediários
No fim, D contém todas as distâncias mínimas
Começa com a matriz de pesos W
Complexidade
Tempo: O(n³)
Espaço: O(n²)
Ideia Central
Usa programação dinâmica
Cria série de matrizes D^(k)
D⁰ = matriz de pesos
Dᵏ[i][j] = min(Dᵏ⁻¹[i][j], Dᵏ⁻¹[i][k] + Dᵏ⁻¹[k][j])
Dⁿ é a matriz de distâncias finais
Aplicações
Inteligência artificial (jogos)
Planejamento de caminhos em robótica
Planejamento de transporte e rotas
Objetivo
Funciona para grafos com pesos não negativos
Similar ao algoritmo de Warshall, mas com pesos
Encontrar distâncias mínimas entre todos os pares de vértices
Algoritmo de Dijkstra
Funcionamento
Inicializa distâncias com ∞, exceto fonte (0)
Enquanto houver vértices não visitados
Seleciona vértice u com menor d[u]
Atualiza distâncias de vizinhos v
Complexidade
O(E log V) (Lista + Min-Heap)
O(V log V + E) (Lista + Fibonacci)
O(V²) (Matriz + Array)
Ideia Central
Usa uma fila de prioridade (min-heap)
Mantém
d[v]: distância mínima conhecida até o vértice v
p[v]: pai (vértice anterior no caminho mais curto)
Exploração em ordem de distância mínima
Aplicações
Redes Sociais
Jogos
GPS
Roteamento
Objetivo
Encontrar o caminho mais curto do vértice fonte para todos os outros
Só funciona com pesos não negativos