Please enable JavaScript.
Coggle requires JavaScript to display documents.
Floyd's Algorithm for the All-Pairs Shortest-Paths Problem - Coggle…
Floyd's Algorithm for the All-Pairs Shortest-Paths Problem
Dado um grafo conectado com pesos, o problema consiste em encontrar o menor caminho dentre todos os pares de caminhos de um vert. para todos os outros
É conveniente armazenar os tamanhos dos menores caminhos em uma matriz D
n x n
chamada de
matriz de distâncias
.
O elemento
Dij
no
i
th linha e
j
th coluna da matriz indica que o tamanho do menor caminho do
i
th vert. para
j
th vert.
Algoritmo de Floyd's
O algoritmo de
Floyd's
serve para gerar essas matriz de distâncias.
O algoritmo pode ser modificado para não encontrar, somente, o tamanhos dos menores caminhos para todos os pares de vert., mas também para os caminhos entre eles.
O algoritmo calcula a matriz de dist. de um grafo com pesos com
n
vert. por meio de uma série de matrizes nxn.
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.
Nós podemos computar todos os elem. de cada matriz D^(K) do antecessor imediato D^(k-1). Seja o elem. dij^(k) da matriz D^(k) significa que é igual para o tamanho do menor caminho entre todos os caminhos de
i
th vert.
vi
ao
j
th
vj
com o núm. de vert. intermediários menores que k.
Também podemos particionar tudo, cada caminho pode ser dividido em dois subambientes.
Entre aqueles que não fazem usem do
k
th vert. v
k
como intermediário e aqueles que usam.
Desde o caminho do primeiro subambiente tem intermediário deles com vert. enumerados não maiores que
k - 1
, o menor dos caminhos deles é dada pela defi. de nossas matrizes.
Já no segundo subambiente, caso no grafo não haja um ciclo de tamanho negativo, podemos limitar a atenção somente para os caminhos no segundo subset que usamos o vert. v
k
como seu vert. intermediário exatamente uma vez(
Cada caminho tem que seguir essa forma.
v
i
, vert. numerados <= k - 1, v
k
, vertices numerados <= k - 1, v
j
.
Em síntese, cada um dos caminhos pode são compostos de dois caminhos. Um caminho que vai de V
i
para V
k
no qual o vert. intermediário não pode ser maior que
k - 1
, e um caminho no qual vai de V
k
para V
j
em que cada vert. intermediário também não ultrapasse
k - 1
O tamanho do menor caminho de Vi para Vk entre os caminhos que usamos com vert. inter. numerados não maiores que k - 1 são iguais a D^(k-1) ik.
O menor caminho de Vk para Vj segue o mesmo racíocinio, porém o tamanho é armazenado no elemento D^(k-1)kj.
Logo, o tamanho do menor caminho em qe usamos
k
th vert. é igual a
D^(k-1) ik + D^(k-1) kj
D^(k)ij = min{ D^(k-1)ik + D^(k-1)kj } for k>= 1, D^(0)ij =Wij
A última matriz na série D^(0) é simplesmente o peso da matriz.
Pode ser aplicado tanto para grafos com pesos com e sem direção no qual não contenham um ciclo de tamanho negativo.
Pseudocódigo
// Implementação do Algoritmo de Floyd's para o problema All-pairs shortest-paths
//
Input:
O tamanho da matriz W de um grafo sem ciclo de tamanho negativo
//
Output:
A dist. da matriz do tamanho do menor caminho
D->W
for
k <-1
to
n
do
for
i<-
to
n
do
for
j <- 1
to
n
do
D[i,j <- min{D[i,j], D[i,k] + D[k,j]}
return D
Tempo de eff. é
Cúbico