Please enable JavaScript.
Coggle requires JavaScript to display documents.
Algoritmos de Caminhos Mínimos - Coggle Diagram
Algoritmos de Caminhos Mínimos
DEFINIÇÃO GERAL
algoritmos que encontram o caminho mais curto entre dois nós
podem lidar com grafos com ou sem pesos, dirigidos ou não dirigidos
ALGORITMO DE DIJKSTRA
OBJETIVO
encontrar o caminho mais curto de um vértice origem para os outros
TIPOS DE GRAFO
pesos não negativos
ESTRUTURA USADA
fila de prioridade (geralmente heap)
COMPLEXIDADE
O(v²) com matriz de adjacenciahv
ETAPAS
inicializa as distancias com infinito
define distancia da origem como zero
itera escolhendo o nó com a menor distancia conhecida
atualiza distancias dos vizinhos
BELLMAN-FORD
OBJETIVO
caminho mais curto de um único vértice para os demais
pode ter pesos negativos
COMPLEXIDADE: O(V x E)
ETAPAS:
inicializa distancias
relaxa todas as arestas V-1 vezes
checa ciclos negativos
FLOYD-WARSHALL
caminhos mínimos entre os pares de vértices
com ou sem pesos negativos (sem ciclos negativos)
ESTRATEGIA: programação dinâmica
ETAPAS:
inicializa matriz de distancias
para cada nó k, tenta relaxar caminhos via
APLICAÇÕES:
Roteamento global, análise de redes, sociometria.
ALGORITMO DE A* (A ESTRELA)
OBJETIVO:
caminho mais curto de um ponto até um destino específico
pesos positivos, geralmente com grade/espacial
HEURÍSTICA:
usa função f(n) = g(n) + h(n)
g(n): custo do início até n
h(n): estimativa do custo de n até o objetivo