Please enable JavaScript.
Coggle requires JavaScript to display documents.
djikstra e outros algoritmos de caminhos mínimos - Coggle Diagram
djikstra e outros algoritmos de caminhos mínimos
Caminhos Mínimos
Encontrar o caminho de menor custo (ou distância) entre vértices de um grafo.
Tipos
De um vértice para todos (single-source)
Entre todos os pares (all-pairs)
Dijkstra
Tipo
Single-source (1 origem → todos os destinos)
Restrição
Não aceita arestas com pesos negativos.
Estratégia
Gulosa (Greedy)
Funcionamento
Começa do nó de origem com distância 0.
A cada passo, escolhe o nó ainda não visitado com menor distância conhecida.
Atualiza distâncias dos vizinhos se encontrar um caminho melhor.
Estrutura auxiliar
Fila de prioridade (Heap)
Complexidade
Com matriz de adjacência: Θ(V²)
Com lista de adjacência e heap: Θ((V + E) log V)
Floyd-Warshall
Tipo
All-pairs (todos os pares de vértices)
Restrição
Permite pesos negativos, mas não ciclos negativos.
Estratégia
Programação dinâmica
Funcionamento
Para cada par (i, j), testa se passar por um vértice intermediário k melhora a distância.
Atualiza: D[i][j] = min(D[i][j], D[i][k] + D[k][j])
Complexidade
Θ(V³)
Bellman-Ford
Tipo
Single-source
Estratégia
Programação dinâmica
Funcionamento
Inicializa todas as distâncias com infinito.
Relaxa todas as arestas V−1 vezes.
Na V-ésima iteração, se ainda for possível melhorar, então há um ciclo negativo.
Complexidade
Θ(V·E)
Aplicações
Grafos esparsos com possibilidade de pesos negativos.
Permite pesos negativos e detecta ciclos negativos