Please enable JavaScript.
Coggle requires JavaScript to display documents.
Caminhos mínimos com fontes multíplas :silhouettes: Alg. de Froyd wharsall…
Caminhos mínimos com fontes multíplas
:silhouettes:
Alg. de Froyd wharsall e Jhonson
Caminhos mínimos com fontes multíplas
O que precisa? :red_flag:
calcular matriz de predecessores
Programação dinâmica.
Definições
Arresta peso negativos :check:
Ciclo com peso negativo :red_cross:
Como funciona?
algoritmo de printar o caminho funciona de maneira recursiva
casos base:
No caso base, se i==j, então ele printa i.
Caso não, mas se πi,j==None, então ele printa que não há caminho entre eles.
Caso contrário, chama a função de forma recursiva e então printa j.
subgrafo dos predecessores de um grafo Gπ,i.
Tempo O(V^4)
Podemos encontrar com alg. já existentes:
:warning:
belleform (quando houve ciclos com peso negativo)
Custo: O(V 2E)
Se o grafo é denso, custo: O(V 4 )
dijkstra (quando não houver ciclo com peso negativo)
Dependendo da estrutura usada:
heap de Fibonacci
→ O(V 2 lg V + VE)
Array
→ O(V 3 + EV) = O(V 3
heap binário
→ O(VE lg V) (melhor se o grafo é esparso)
aplicar |V| vezes a mais
Conceitos importantes:
:warning:
Estrutua do caminho minimo tem m-1 aresta
quando não houver ciclo
Caminhos mínimos e multiplicação de matrizes
Em relação a eficiência
É melhor que bellman ford.
Não é melhor que dijkstra aplicado |N| vezes.
Melhorando o Desempenho
É possível obter L (n-1) com o teto de lg(n-1)
Dobra a quantidade de N
Exponencialmente.
Agora se torna viável o uso
ao invés do dijkstra
Melhora o tempo O(V^4) -> O(V^3 lg V)
Utiliza programação dinâmica
Algoritmos de Grafos:
Algoritmo de Floyd-Warshall e Algoritmo de Johnson
Floyd-Warshall
Conceitos:
Técnica se baseia na programação dinâmica
Utiliza vértices intermediários de i ~> j
Explora relação de i -->
k
~> j
k vértice intermediário
Tempo O(n³)
A ideia
Verifica se k é um vértice intermediário do percurso p
Se não descarta o K
se o k = 0 não tem caminho
Se sim, decompõe recursivamento i -->
k
~> j
p1 - de i ~> k
p2 - de k ~> j
faz k − 1 e retorma a recurssão
Método alternativo
Troca os seguintes operações
Troca o min e + pelo no alg Floyd-Warshal
por OR ou AND
Fica binário
"+ velocidade e - espaço"
Da Completude Transitiva de um Grafo Dirigido
Detecta ciclos de custo negativo
Johnson
Conceitos
Para grafos esparsos
Se forem densos fica na ordem de O(n³)
menos custoso
Usa:
Dijkstra
Bellman-ford
Tempo
O(V² lg V + VE)
Como funciona?
Técnica de Reponderamento
Preservação de Caminhos Mais Curtos pelo Reponderamento:
Demonstrado que o reponderamento não altera os caminhos mais curtos.
Liga um novo Vértice S a todos os Vértices
com peso 0
Calcula
ŵ(u, v) = w(u, v) + h(u) − h(v).
Passos do alg.
:warning:
Constroi grafo G linha
roda o alg. de bellman-ford sobre G linha
Ajusta h(v)
δ (s,v) usando as informações do Bellman-Ford.
Computa os novos pesos
Calcula novos pesos ŵ
garantindo a ausência de ciclos negativos
Calcula o percurso masi curto usando dijkstra
no grafo com os novos pesos
retorna a matriz D
Se não for esparso, melhor usar:
:warning:
Implementando com o heap de fibonacci
Tira o (min(d (k−1) ij , d (k−1) ik + d (k−1) kj ))