Please enable JavaScript.
Coggle requires JavaScript to display documents.
Dijkstra e Floyd-Warshall - Coggle Diagram
Dijkstra e Floyd-Warshall
Problema do menor caminho a partir de uma fonte (single-source shortest path)
Dado um vértice fonte em um grafo ponderado e conectado (dirigido ou não), encontrar o menor caminho até todos os outros vértices
Não é o mesmo que o caminho mais curto passando por todos os vértices (TSP)
Aplicações: transporte, redes, jogos, robótica, compiladores, etc.
Algoritmo de Dijkstra
Resolve: menor caminho a partir de uma fonte, para todos os vértices (com todos os pesos não-negativos)
Ideia geral:
Mantém dois conjuntos: vértices já com menor caminho encontrado (VT), e os "fringe" (candidatos, na fila de prioridade)
A cada passo, escolhe o vértice de menor distância atual na fila (menor d[v] entre os fringe/candidatos)
Atualiza as distâncias dos vizinhos do vértice escolhido, se encontrar um caminho mais curto
Repete até visitar todos os vértices
Estrutura fundamental: fila de prioridade (tipicamente um heap mínimo)
Cada vértice armazena:
d[v]: distância mínima conhecida até agora a partir da fonte
p[v]: predecessor de v no caminho mais curto
Pseudocódigo resumido:
Inicializa todos d[v] = ∞, p[v] = null; d[fonte] = 0
Coloca todos os vértices na fila de prioridade (com prioridade d[v])
Enquanto a fila não está vazia:
Remove vértice u com menor d[u]
Para cada vizinho v de u:
Se d[u] + w(u, v) < d[v], atualiza d[v] e p[v], e atualiza prioridade de v na fila
Eficiência:
Matriz de pesos + vetor comum: O(V^2)
Lista de adjacências + heap mínimo: O(E log V)
Lista de adjacências + Fibonacci heap: O(V log V + E) (teórico)
Restrições: não funciona com pesos negativos
Algoritmo de Floyd-Warshall
Resolve: menor caminho entre todos os pares de vértices (all-pairs shortest path)
Aplicável para grafos ponderados (dirigidos ou não), sem ciclos de peso negativo
Ideia geral:
Mantém uma matriz D[i][j]: menor caminho conhecido de i para j
Inicialização: D[i][j] = peso da aresta (i, j) se existir, senão ∞; D[i][i]=0
Para cada vértice k de 1 a n:
Para cada par (i, j):
D[i][j] = min(D[i][j], D[i][k] + D[k][j])
Depois de todos os n passos, D[i][j] é o menor caminho de i para j
Eficiência: O(n^3), onde n é o número de vértices
Permite, além dos valores mínimos, reconstruir o caminho (com matriz de predecessores)
Serve para grafos densos ou quando precisa de todos os caminhos mínimos