Please enable JavaScript.
Coggle requires JavaScript to display documents.
SHORTEST PATHS OTHERS - Coggle Diagram
SHORTEST PATHS OTHERS
-
Bellman-Ford algorithm
-
-
-
-
-
Iteração k =| V | − 1: se algo melhor
for encontrado, há um ciclo negativo
Eficiência de tempo em theta(| V || E |) = theta(|V|^3), desde que |E| ∈ O(|V|^2)
Dado um grafo conectado ponderado (não direcionado ou direcionado), os caminhos mais curtos de todos os pares se preocupam em encontrar as distâncias – ou seja, os comprimentos dos caminhos mais curtos – de cada vértice para todos os outros vértices.
É conveniente registrar os comprimentos dos caminhos mais curtos em uma matriz n × n D chamada matriz de distância: o elemento d(ij) da i-ésima linha e j-ésima coluna dessa matriz indica o comprimento do caminho mais curto do vértice i ao vértice j.
A matriz de distância pode ser gerada a partir do Floyd’s algorithm, o qual pode ser aplicado tanto em grafos direcionados quanto não direcionados, desde de que não tenham um ciclo de comprimento negativo.
O algortimo pode ser aprimorado não só para encontrar o comprimento dos menores caminhos para os pares de vértices, como também os próprios caminhos mais curtos.
O algoritmo de Floyd calcula a matriz de distância de um gráfico ponderado com n vértices através de uma série de n×n matrizes: D^(0),...,D^(k−1),D^(k),...,D^(n).
Cada uma dessas matrizes contém os comprimentos dos caminhos mais curtos com certas restrições nos caminhos considerados para a matriz em questão.
Aplicações: comunicações, redes de transportes, pesquisa operacional, pré-computação de distâncias para planejamento de movimento em jogos de computador.