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
Dijkstra - Caminho mínimo a partir de um único vértice
Estratégia: Greedy
Não permite pesos negativos
Usa fila de prioridade (heap)
Inicializa distâncias com ∞, exceto a origem (0)
Insere origem no heap
Enquanto houver vértices não visitados:
3.1. Remove o vértice com menor distância
3.2. Marca como visitado
3.3. Relaxa vizinhos com:
D[w] > D[v] + peso(v, w) → atualiza distância
Sem Heap: Θ(V²)
Com Heap: Θ((V + E) log V)
Aplicações
Planejamento de rotas
Robótica e jogos
Redes sociais
GPS e mapas
Bellman-Ford
Caminho mínimo a partir de um único vértice
Permite pesos negativos
Detecta ciclos negativos
Estratégia: Programação dinâmica
Inicializa distâncias com ∞, exceto a origem
Para k = 1 até V−1:
2.1.Relaxa todas as arestas
Verificação final:
3.1.Se ainda houver atualização → ciclo negativo
Θ(V·E) (ou Θ(V³) se grafo for denso)
Aplicações
Arbitragem em mercados financeiros
Roteamento com penalidades
Planejamento sob incerteza
Floyd-Warshall
Caminhos mínimos entre todos os pares de vértices (all-pairs)
Permite pesos negativos
Não permite ciclos negativos
Estratégia: Programação dinâmica
Para cada vértice intermediário k:
Para todos os pares (i, j):
2.1. D[i][j] = min(D[i][j], D[i][k] + D[k][j])
Θ(V³)
Aplicações
Mapas completos
Análise de acessibilidade
Redes de comunicação internas