Please enable JavaScript.
Coggle requires JavaScript to display documents.
MM7 - Coggle Diagram
MM7
-
All-Pairs Shortest Paths
- All-Pairs Shortest Paths (APSP): encontrar a menor distância entre todos os pares de vértices
- Usado para responder consultas de caminhos mínimos em grafos
-
- Complexidade O(V³) devido aos três laços
- Pré-condição: matriz de adjacência com pesos dos arcos ou INF onde não existe aresta
- Implementação: laços k, i, j na ordem k->i->j
- Atualização: AdjMat[i][j] = min(AdjMat[i][j], AdjMat[i][k] + AdjMat[k][j])
-
- Dijkstra: V chamadas, O(V³ log V) no caso denso
- Bellman-Ford: V chamadas, O(V⁴) no caso denso
- Floyd Warshall é melhor para V ≤ 400
- Ideia principal: aos poucos permitir intermediários [0..k]
- sp(i,j,k): menor caminho de i para j usando intermediários [0..k]
- Começa com arestas diretas (k = -1)
- A cada k, permite novos caminhos usando k como intermediário
- Transitive Closure (Warshall): verifica se i é conectado a j direta ou indiretamente
- Minimax/Maximin Path: encontra custos minimax alterando tipo de atualização
- Detecção de ciclos e ciclo negativo: verifica diagonal na pós execução
- Diâmetro do grafo: maior entre os menores caminhos
- SSSP para grafos pequenos: facilita código em vez de Dijkstra
- Encontrar SCCs: após Warshall, se AdjMat[i][j] e AdjMat[j][i], pertencem à mesma SCC
- INF = 1e9 para evitar overflow, não usar MAXINT
- Arestas negativas: pode detectar ciclo negativo, mas caminhos podem ficar indefinidos se houver ciclos negativos