Algoritmo busca-ciclos de Floyd - envio

Prévia do material em texto

Algoritmo busca-ciclos de Floyd
Aluna: Viviane 
Curso: Ciência da Computação
Matéria: Análise de Computabilidade e Complexidade de Algoritmos
Definição:
Algoritmo criado  para resolve o problema de calcular o menor caminho entre todos as duplas de vértices em um grafo orientado.
Foi detalhado por Bernard Roy em 1959 e mais tarde ( 3 anos) por Stephen Warshall e Robert Floyd.
Ele encontra os valores e não o caminho de arestas a ser percorrido.
Esse algoritmo utiliza matrizes para definir os caminhos mínimos entre todos os pares de nós da rede, são executadas n interações que corresponde ao número de nós. A cada interação corresponde uma matriz em que os valores são modificados utilizando uma equação de recorrência:
Determina-se primeiramente a matriz D0 cujos valores correspondem aos comprimentos dos arcos se estes existem, caso contrario os valores são ∞. Depois se calcula D1 de D0 e D2 de D1 até se obter Dn de Dn-1. 
A matriz Dn é a matriz final que mostra as distâncias mínimas entre todos os nós da rede. A ideia deste algoritmo é verificar a cada iteração se ao incluir um nó k intermediário no caminho de i para j pode ser reduzido o tamanho de um caminho já determinado. 
Para isso numera-se os nós do grafo de n. Definamos a matriz D0 cujos valores d correspondem ao comprimento dos arcos (i, j) caso exista o arco no grafo; caso contrário considere d ∞, e faça os elementos da diagonal da matriz, d para todo i. 
Para cada k = 1,...,n determine sucessivamente os elementos da matriz Dk a partir dos elementos da matriz Dk-1 utilizando a equação informada acima. Este processo é feito até k = n, e com isso o valor do caminho mínimo de todos os pares (i, j) do grafo estão definidos na matriz Dn.
 Entrada: Grafo ponderado G=(N,E). As arestas podem ter valores negativos, no entanto os grafo não se podem ter nenhum ciclo de valor negativo. 
Saída: Matriz n n com os custos dos menores caminhos entre todos os nós de N
Exemplos de aplicações: 
· Calcular o Fecho Transitivo de um grafo;
· Verificar se um grafo não-dirigido é bipartido;
· Achar um vértice central, isto é, aquele que minimiza a distância
· máxima ou média entre todos os vértices;
Fonte: https://pt.slideshare.net/JoaoSilva30/algoritmo-de-floydwarshall
Fontes:
1. https://pt.wikipedia.org/wiki/Algoritmo_de_Floyd-Warshall
2. https://docs.ufpr.br/~volmir/PO_II_10_caminho_minimo.pdf
3. https://pt.slideshare.net/JoaoSilva30/algoritmo-de-floydwarshall
2