Algoritmos do caminho eureliano tipo floyd

Disponível somente no TrabalhosFeitos
  • Páginas : 2 (439 palavras )
  • Download(s) : 0
  • Publicado : 22 de janeiro de 2013
Ler documento completo
Amostra do texto
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 RobertoMoraes Ricardo Castro [Ricardo_idt@hotmail.com] RA 202501 Sorocaba – SP/BR, Outubro de 2004

• Descrição Sucinta do Programa Este algoritmo é usado para encontrar os caminhos de menor valor entretodos 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, é precisoconstruir 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 existeuma 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 é colocadotambé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 ipara 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 paracalcular 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 menorcusto 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...
tracking img