Algoritmos do caminho eureliano tipo floyd

Algoritmos do Caminho Eureliano Tipo Floyd
Faculdade de Engenharia de Sorocaba – FACENS Departamento de Coordenação Engenharia da Computação Estrutura de Dados e Algoritmos – Prof. Celso Roberto Moraes Ricardo Castro [[e-mail]] RA 202501 Sorocaba – SP/BR, Outubro de 2004

• Descrição Sucinta do Programa Este algoritmo é usado para encontrar os caminhos de menor valor entre todos os vértices em um grafo. Isto é feito operando em uma matriz que representa os custos de todas as arestas entre vértices

• Operação do Programa Antes de aplicar o algoritmo de Floyd, é preciso construir uma matriz quadrada de tamanho n, onde n é o número de vértices do grafo. Cada linha na matriz representa um vértice origem, enquanto cada coluna representa um vértice destino. Se existe uma aresta entre os vértice i e j no grafo, o custo desta aresta é colocado na posição (i, j) da matriz. Se o grafo for nãoorientado ou todas as arestas forem bidirecionais, este valor é colocado também na posição (j, i) da matriz. Se não existe nenhuma aresta ligando diretamente os dois vértices, um valor infinito é colocado na posição (i, j) para especificar que é impossível ir diretamente de i para j. • Algoritmo Utilizado Algoritmo Relacionado tipo Floyd. • Condições de Contorno O algoritmo faz uso de matrizs, onde quando esta esteja preenchida, o algoritmo de Floyd pode ser usado para calcular a menor distância entre todos os pontos do grafo.

• Testes O programa foi testado diversas vezes e quando esta rotina acaba, os valores em todas as posições da matriz representam o menor custo entre os vértices das linhas e os das colunas. • Dificuldades Encontradas A nossa maior dificuldade foi além de tempo para maiores pesquisas, também na elaboração e tentativa da lógica do código “pseudo-código” e estrutura .

• Especificação Implementada O programa implementou todos os requisitos fornecidos na especificação.

• Sugestões 3 É fácil observar que o algoritmo de Floyd tem complexidade