Please enable JavaScript.
Coggle requires JavaScript to display documents.
Capítulo 4: Graphs Parte 3 - Coggle Diagram
Capítulo 4: Graphs Parte 3
4.4 SINGLE-SOURCE SHORTEST PATHS
4.4.5 Comparação Geral
Floyd-Warshall (alternativa) → O(V³) p/ grafos pequenos
Bellman-Ford → O(VE), pesos negativos
Dijkstra → O((V + E) log V), pesos ≥ 0
BFS → O(V + E), não ponderado
4.4.4 SSSP com Pesos Negativos
Uso: arbitragem, fluxo de dinheiro, dívidas
Relaxa todas as arestas V−1 vezes
Detecta ciclos negativos (checando após V-1 iterações)
Complexidade: O(V × E)
Algoritmo: Bellman-Ford
4.4.3 SSSP em Grafos Ponderados (positivos)
Uso: redes de transporte, rotas com custo positivo
Variações: lazy deletion / várias entradas no heap
Relaxamento: dist[v] = min(dist[v], dist[u] + w)
Complexidade: O((V + E) log V)
Estrutura: min-heap (priority_queue)
Algoritmo: Dijkstra
4.4.2 SSSP em Grafos Não Ponderados
Uso típico: grids, labirintos, conexões simples
Extensão: Multi-Source BFS (várias origens)
Estrutura: fila (queue)
Distância = nº mínimo de arestas
Complexidade: O(V + E)
Algoritmo: BFS
4.4.1 Overview and Motivation
Aplicações: rotas, custos mínimos, propagação de informação
Três abordagens principais:
Bellman-Ford → pesos negativos (detecta ciclos)
Dijkstra → pesos positivos
BFS → grafos não ponderados
Problema: menor caminho de 1 vértice fonte → todos os outros
4.5 ALL-PAIRS SHORTEST PATHS
4.5.1 Overview and Motivation
Problema: menor caminho entre todos os pares (i, j)
Solução clássica: Floyd–Warshall
Complexidade: O(V³)
Aplicável para V ≤ 400 (grafos pequenos)
4.5.2 Floyd–Warshall – Formulação DP
Conceito: cada vértice k é permitido como intermediário
Recorrência: Dᵏ[i][j] = min(Dᵏ⁻¹[i][j], Dᵏ⁻¹[i][k] + Dᵏ⁻¹[k][j])
Atualização em 3 loops: k → i → j
Usa matriz de adjacência (AdjMat)
Redução de 3D → 2D (mesma matriz atualizada)
4.5.3 Outras Aplicações do Floyd–Warshall
(a) Resolver SSSP em grafo pequeno
(b) Imprimir caminhos (matriz de predecessores p[i][j])
(c) Transitive closure (conectividade lógica)
(d) Minimax / Maximax (mínimo do máximo)
(e) Detectar ciclos negativos (Adj[i][i] < 0)
(f) Encontrar diâmetro do grafo (maior dist. finita)
4.5.4 Comparativo entre Algoritmos
BFS → SSSP unweighted → O(V + E)
Dijkstra → SSSP positive → O((V + E) log V)
Bellman-Ford → SSSP general → O(VE)
Floyd–Warshall → APSP → O(V³)