Stack Overflow em Português é um site de perguntas e respostas para programadores profissionais e entusiastas. Leva apenas um minuto para se inscrever.
Estou a tentar implementar o algoritmo de Dijkstra, criando uma função em Pascal.
Tenho algo como:
function Dijkstra(L:mapa):integer;
begin
min := max ;
map.mini:= 0;
for i := 2 to min do
if L.matriz[i,j] < map.mini then
begin
min:= L.matriz[i,j];
map.mini := i;
end;
Dijkstra:=map.mini ;
end;
Até onde cheguei não está a funcionar, alguma sugestão?
Esse seu algoritmo não está muito parecido com o de Dijkstra...
– Andre Figueiredo15/11/14 às 14:59
2
E a qual dos algoritmos de Dijkstra vc se refere?
– Bacco♦15/11/14 às 17:35
preciso de este aqui função Dijkstra(L = [1..n, 1..n]: grafo): vetor[2..n] C := {2,3,...,n} Para i := 2 até n: D[i] := L[1,i] P[i] := 1 Repetir n-2 vezes: v := Elemento de C que minimiza D[v] C := C - {v} Para cada elemento w de C: Se D[w] > D[v]+ L[v,w] então D[w] := D[v]+ L[v,w] P[w] := v Retornar P
– concessio17/11/14 às 13:23
Encontrei essa resposta no livro PASCAL ESTRUTURADO 3
Edição Editora LTC 1999
Dos autores :
Harry Farrer
Christiano Gonçaves Becker
Eduardo Chaves Faria
...
Exemplo 2.27 página 77..
Os nós no gráfico apresentado a seguir representam as cidades e os arcos a presença de uma estrada ligando duas cidades os números ao lado dos Arcos representa a distância em quilômetros.
Pode se representar,numericamente, este grafo por uma variável composta bidimensional ,na qual a distância entre duas cidades i,j é indicado pelo elemento D(i,j; se i=j ou se não houver conexão entre i e i. D(i.i) será zero. Dessa forma tem-se:
O problema consiste, então, em se achar o caminho mais curto entre duas cidades quaisquer. Este problema foi resolvido por Dijkistra [DIJKISTRA, 1971] e tem uma série de aplicação de questões de otimização.
Além da matriz D das distâncias, considera-se a variável composta unidimensional DA,
cuja componente DA[I] representa a distância acumulada em um caminho percorrido desde a
origem até a cidade I. Cada uma destas componentes será iniciada com um valor bem grande, por exemplo 10000.
Ainda serão consideradas mais duas variáveis compostas unidimensionais. A primeira, designada Ant, será tal que a sua componente Ant[I] indica qual é a cidade antecedente de I no caminho considerado. A outra ExpA, terá componentes lógicas "expandidas".
Partindo de uma cidade C inicialmente igual a origem, calcula-se a nova distância acumulada (NovaDA) de cada uma das cidades adjacentes a C ainda não expandidas. A nova distância acumulada prevalecerá sobre o valor anterior se lhe for inferior, neste caso ,C será atribuído a componente Ant[I]. Quando terminar a expansão de C, registra-se que ExpA[C] é verdadeiro.
Em seguida, procura-se, dentre as cidades ainda não expandidas, aquelas que têm a menor distancia acumulada. Esta será a nova cidade C, e a sua distancia acumulada é, então, a menor que possa ser conseguida a partir da Origem.
O processo será repetido até que a cidade C seja o Destino ou que não se encontre nenhuma cidade ainda não expandida, cuja distancia acumulada seja inferior a 10000. Neste último caso, isto significa que não existe caminho ligando a Origem ao Destino.
Aqui esta o algoritmo em linguagem pascal:
program Dijkistra;
var D: array[1..100, 1..100] of integer;
DA, Ant: array[1..100] of integer;
ExpA: array[1..100] of boolean;
N, Origem, Destino, I, J, C, NovaDA, Min: integer;
begin
readln(N);
for I:= 1 to N do
begin
for J:= 1 to N do
read(D[I,J]);
readln;
end;
readln(Origem, Destino); { atribuição de valores iniciais necessários}
for I:= 1 to N do
begin
ExpA[I]:= false;
DA[I]:= 10000
end;
C:= origem;
DA[C]:= 0;
while (C <> Destino) and(C <> 0) do
begin {Expanção de C}
for I:= 1 to N do
if (D[C, I] <> 0) and(not Expa[i])
then begin
NovaDA:= DA[C] + D[C, I];
if NovaDA < DA[I]
then begin
DA[I]:= NovaDA;
Ant[I]:= C
end
end;
Expa[C]:= true; {Determinação do proximo C}
Min:= 10000;
C:= 0;
for I:= 1 to N do
if (not ExpA[I]) and (DA[I] < Min)
then
begin
Min:= DA[I];
C:= I;
end;
end;
if C = Destino
then begin
writeln('Caminho mais curto');
writeln(C);
while C <> Origem do
begin
C:= Ant[C];
writeln(C)
end
end
else writeln('Não existe caminho unindo as duas cidades');
end.
Como assim? Eu não tenho a referência do livro! Use o link de editar que está logo abaixo da sua resposta e coloque a referência. Recomendo também deixar claro o que é texto seu e o que é transcrição do livro (pode usar > no começo da linha para formatar como citação).
– bfavaretto♦10/09/15 às 2:37