Responder 
 
Avaliação do Tópico:
  • 0 Votos - 0 Média
  • 1
  • 2
  • 3
  • 4
  • 5
Algoritmo de Floyd
12/10/2012, 16:47 (Resposta editada pela última vez em: 12/10/2012 23:35 por tiago1.)
Resposta: #1
Algoritmo de Floyd
Olá a todos,

Pessoal, estou aprendendo em aula o algoritmo de Floyd, usado pra roteamento em redes e estou tendo dificuldades em escrever ele em VisualG (sei que é antiga essa ferramenta, mas acho ela bem legal).
Eu preciso fazer a matriz carregar os valores diretamente, sem ter de ficar digitando 1 por 1. A ideia é fazer com que o algoritmo pergunte "Digite a rota inicial" e depois "Digite o destino" e depois mostre na tela os roteadores que passou.

Eis o algoritmo:

Código:
Entrada: Matriz de Custos D
Saída:             A -> Matriz com os comprimentos dos menores caminhos
                R -> Fornece o vértice k que é o primeiro a ser visitado no menor caminho de vi até vj.
Início
     Para i =1 até n Faça
         Para j = 1 até n Faça
             A[i,j] <- D[i,j];
             R[i,j] <- j;
     Para i = 1 até n Faça
         A[i,i] <- 0;
     Para k = 1 até n Faça
         Para i = 1 até n Faça
             Para j = 1 até n Faça
                 Se A[i,k] + A[k,j] < A[i,j] então {aplica-se a função aqui (não consigo escrever aqui)
                     A[i,j] <- A[i,k]+A[k,j];
                     R[i,j] <- k;
Fim

E aqui mostro o que já consegui passar pro VisualG:

Código:
algoritmo "floyd"
//Entrada: Matriz de custos D
//Saída:  A -> Matriz com os componentes dos menores caminhos
//        R -> Fornece o vértice k que é o primeiro a ser visitado no menor caminho de vi até vj
var
R:vetor[1..6,1..6] de inteiro
A:vetor[1..6,1..6] de inteiro
D:vetor[1..6,1..6] de inteiro
i,j,k:inteiro
inicio
para i de 1 ate 6 faca
   para j de 1 ate 6 faca
      A[i,j] <- D[i,j]
      R[i,j] <- j
   fimpara
   para i de 1 ate 6 faca
      A[i,i] <- 0
   fimpara
   para k de 1 ate 6 faca
      para i de 1 ate 6 faca
         para j de 1 ate 6 faca
            se A[i,k] + A[k,j] < A[i,j] entao  //aplica-se a função
               A[i,j] <- A[i,k] + A[k,j]
               R[i,j] <- k
            fimse
         fimpara
      fimpara
   fimpara
fimpara
fimalgoritmo
a função do algoritmo de Floyd, tentarei "ditar" aqui: d ij elevado a k = MIN[d ij elevado a k-1,(d ik elevado a k-1 + d kj elevado a k-1)]
Eu não sei se dá pra por uma imagem da função aqui n fórum. =(

Também não consegui entender o que é esse "k" no algoritmo, estou tentando entender. =(

A matriz é 6x6, tamanho fixo.

Agradeço se alguém puder se manifestar a respeito.

Obrigado!
Encontrar todas as respostas deste usuário
Citar esta mensagem em uma resposta
Responder 


Ir ao Fórum:


Usuários visualizando este tópico: 1 Visitantes

Entre em Contato | Fórum Debian | Voltar ao Topo | Voltar ao Conteúdo | Modo Leve (Arquivo) | Feeds RSS