Я может уже повторяюсь, но мне нужна реализация алгоритма Дейкстры на pascal. Какую-нибудь простенькую задачку (нужно разобраться). Мне нужна именно реализация алгоритма, а не сам алгоритм (я его хорошо знаю). Почти все известные алгоритмы уже разобрал, а вот Дейкстры никак не найду, а сам чё-то никак. Помогите кто чем может
P.S На форуме нашел задачу, но там считывается из файла, а файл представляет из себя комбинацию цифр. Ни чё не понял
мисс_граффити
2.09.2007 18:28
речь про этот алгоритм? а в чем проблема с реализацией? вроде как все подробно описано...
striker
3.09.2007 15:41
Вот исходник взял в FAQ:
UNIT Dijkstra;
InterfaceConst
NN=30;
Type
graph=array [1..nn,1..nn] of integer;
procedure Deikstr(n:integer; W:graph; u1,u2:integer;
var length:integer; var Weight:real; var Path: arrayof integer);
Implementationprocedure Deikstr(n:integer; W:graph; u1,u2:integer;
var length:integer; var Weight:real; var Path: arrayof integer);
var
i,k,j:integer;
GM:real;
d,m:array[1..nn] of real;
p:array[1..nn] of integer;
t:integer;
dd,min:real;
begin
GM:=10000;{бесконечность}
length:=0;
if u1<>u2 thenbegin
i:=1;
repeat
d[i]:=GM; p[i]:=0; m[i]:=0; i:=i+1untilnot(i<=n);
d[u1]:=0; t:=u1;
while length=0dobegin
i:=1;
repeatif w[t,i]<GM thenbegin
dd:=d[t]+w[t,i];
if d[i]>dd thenbegin d[i]:=dd; p[i]:=t end;
end;
i:=i+1untilnot(i<=n);
Min:=GM; i:=1; k:=0;
repeatif m[i]=0thenbeginif d[i]<min thenbegin min:=d[i]; k:=i end;
end;
i:=i+1untilnot(i<=n);
if k<>0thenbegin
m[k]:=1; t:=k;
if t=u2 thenbegin length:=1; end;
endelsebegin length:=-1end;
end;
if length=1thenbegin
Path[1]:=u2; length:=2; j:=u2;
repeat
Path[length]:=P[j]; j:=P[j]; length:=length+1untilnot(j<>u1);
i:=1; k:=trunc(length/2);
repeat
t:=Path[i]; Path[i]:=Path[length-i]; Path[length-i]:=t; i:=i+1untilnot(i<=k);
length:=length-1end;
Weight:=d[u2]
end;
end;
end.
uses wincrt,dijkstra;
var
i,u1,u2,n,l:integer;
G:Graph;
w:real;
path:array[0..100] of integer;
procedure ReadFileGraph(var a:graph);
var
i,j:integer; filename:string; f:text;
begin
Write('Enter file name:'); readln(filename);
Assign (f,filename); reset(f);
Readln(f,N);
For i:=1to n dofor j:=1to n do read(f,a[i,j]); close(f);
end;
begin
readfilegraph(G); {читаем из файла граф.}
write('u1 = '); readln(u1); {вводим первую вершину}
write('u2 = '); readln(u2); {...и конечную..}
Deikstr(n,G,u1,u2, L,w,path);
writeln('w=',w:1:2); {выводим минимальный путь (вес)}
writeln('path'); {выводим путь ....}for i:=1to l do write(path[i],' - ');
readkey;
end.
А это содержимое файла, из которого считывается граф.
Разобрался почти во всём. Вопрос вот в чём: Как описывается в файле граф? Что это за числа(понимаю, что , но не знаю именно как перечисляются) И что происходит здесь:
Код
while length=0 do begin i:=1; repeat if w[t,i]<GM then begin dd:=d[t]+w[t,i]; if d[i]>dd then begin d[i]:=dd; p[i]:=t end; end; i:=i+1 until not(i<=n); Min:=GM; i:=1; k:=0;
И здесь:
Код
begin Path[1]:=u2; length:=2; j:=u2; repeat Path[length]:=P[j]; j:=P[j]; length:=length+1 until not(j<>u1); i:=1; k:=trunc(length/2); repeat t:=Path[i]; Path[i]:=Path[length-i]; Path[length-i]:=t; i:=i+1 until not(i<=k); length:=length-1 end; Weight:=d[u2] end;
Понятно, что путь ищется, но как?
Вот граф
volvo
3.09.2007 16:12
Цитата
Понятно, что путь ищется, но как?
А, прости, тебе для чего ссылку на описание алгоритма привели? Чтобы опять теперь "пережевывать" то, что должно быть понятно из теоретического описания? Будь добр прочесть то, что написано в описании алгоритма (и не только на АлгЛибе, AlgoList насколько я помню, тоже содержит описание алгоритма: Алгоритм Дейкстры, да описание есть практически на любом сайте), разобраться, как оно ДОЛЖНО работать, а потом уже задавать вопросы как оно РАБОТАЕТ в какой-то определенной реализации...
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.
