Algoritmo de Floyd [RESOLVIDO]

tiago1
(usa Ubuntu)

Enviado em 12/10/2012 - 16:00h

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:

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:

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!

tiago1
(usa Ubuntu)

Enviado em 12/10/2012 - 16:03h

Aqui no VisualG estava identado corretamente, mas quando colei os códigos no fórum, eles se desconfiguraram, desculpe. =/

tiago1
(usa Ubuntu)

Enviado em 12/10/2012 - 23:34h

Aee, agora deu certo, usei o code e o /code, hehehe!

Não tinha me ligado deste recurso. =)

tiago1
(usa Ubuntu)

Enviado em 14/10/2012 - 14:12h

Pessoal, consegui carregar os valores na matriz D sem ter de ficar digitando, assim:

algoritmo "defloyd"

var

R:vetor[1..7,1..7] de inteiro

A:vetor[1..7,1..7] de inteiro

D:vetor[1..7,1..7] de inteiro

i,j,k:inteiro

inicio

D[1,1] <- 0

D[1,2] <- 999

D[1,3] <- 2

D[1,4] <- 999

D[1,5] <- 7

D[1,6] <- 999

D[2,1] <- 3

D[2,2] <- 0

D[2,3] <- 999

D[2,4] <- 999

D[2,5] <- 999

D[2,6] <- 6

D[3,1] <- 999

D[3,2] <- 999

D[3,3] <- 0

D[3,4] <- 4

D[3,5] <- 999

D[3,6] <- 999

D[4,1] <- 999

D[4,2] <- 999

D[4,3] <- 999

D[4,4] <- 0

D[4,5] <- 4

D[4,6] <- 999

D[5,1] <- 999

D[5,2] <- 5

D[5,3] <- 6

D[5,4] <- 999

D[5,5] <- 0

D[5,6] <- 999

D[6,1] <- 999

D[6,2] <- 999

D[6,3] <- 4

D[6,4] <- 999

D[6,5] <- 999

D[6,6] <- 0

escreval("Digite o ponto inicial")

leia(A[i,j])

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

               A[i,j] <- A[i,k] + A[k,j]

               R[i,j] <- k

            fimse

         fimpara

      fimpara

   fimpara

fimpara

escreval(A[i,j])

escreval(R[i,j])

fimalgoritmo

 

Onde está escrito "999" são os valores que representam o infinito.
As matrizes A e R são respectivamente as matrizes com os menores caminhos e a R é dos cominhos de roteamento.
Eu entendi como funciona o algoritmo, sei que o remetente é a linha e o destino é a coluna, são nesses cruzamentos que se acham os roteadores do caminho, mas não estou conseguindo implementar ele pra que mostre os roteadores que são percorridos no trajeto.

Alguém tem alguma ideia de como seria?

Obrigado!