Matriz de cadeias
algoritmo()
{
// calcula a menor distancia entre duas cidades
matriz inteiro Distancia[6:6];
// matriz das distancias entre as cidades
matriz inteiro Acumulada[6];
// distancia acumulada no percurso ate i
matriz inteiro CidadeAnterior[6];
// cidade anterior a i no percurso
matriz inteiro Percurso[6];
inteiro i; // indexador para as linhas da matriz
inteiro j; // indexador para as colunas da matriz
inteiro origem; // numero que identifica a cidade de origem
inteiro destino;
// numero que identifica a cidade de destino
inteiro DistanciaMinima;
// distancia minima entre origem e destino
inteiro cidade; // cidade de inicio do percurso
inteiro NovaDistancia; // nova distancia acumulada
ascii RESP;
inteiro NumCidades;
// leitura da tabela das distancias entre as cidades
NumCidades := 6;
para ( i := 1 ate NumCidades passo 1 )
{
para ( j := 1 ate NumCidades passo 1 )
{
leia ( Distancia [i,j] );
/*
leia("cidades ", i, " e ", j, " = ", Distancia[i,j]);
leia(d[i,j], "cidades ", i, " e ", j, " = ", d[i,j]);
*/
}
}
// inicializa os vetores
para ( i := 1 ate NumCidades passo 1 )
{
Percurso[i] := 0;
Acumulada[i] := 10000;
}
RESP := 'S';
repita
{
leia ("informe a cidade de origem: ", origem);
leia ("informe a cidade de destino: ", destino);
cidade := origem;
Acumulada[cidade] := 0;
i:=1;
repita
{
i := 1;
repita
{
se (Distancia[cidade,i] <> 0 & Percurso[i] == 0)
{
NovaDistancia := Acumulada[cidade] +
Distancia[cidade,i];
se (NovaDistancia < Acumulada[i])
{
Acumulada[i] := NovaDistancia;
CidadeAnterior[i] := cidade;
}
}
i := i + 1;
} ( i > NumCidades );
Percurso[cidade] := 1;
DistanciaMinima := 10000;
cidade := 0;
i := 1;
repita
{
se (Acumulada[i] < DistanciaMinima &
Percurso[i] ==0)
{
DistanciaMinima := Acumulada[i];
cidade := 1;
}
i := i + 1;
} ( i > NumCidades );
escreva ("cidade = ", cidade, " destino = ", destino);
} ( cidade == destino | cidade == 0 );
se ( cidade == destino )
{
repita ( cidade == origem )
{
escreva (cidade);
cidade := CidadeAnterior[cidade];
}
}
senao
{
escreva ("nao existe caminho unindo as duas cidades");
}
leia ( "deseja continuar (s/n): ", RESP );
} ( RESP == 'N' | RESP == 'n' );
}