Версия для печати темы

Автор: striker 2.09.2007 0:37

Я может уже повторяюсь, но мне нужна реализация алгоритма Дейкстры на pascal.
Какую-нибудь простенькую задачку (нужно разобраться).
Мне нужна именно реализация алгоритма, а не сам алгоритм (я его хорошо знаю).
Почти все известные алгоритмы уже разобрал, а вот Дейкстры никак не найду, а сам чё-то никак.
Помогите кто чем может

P.S На форуме нашел задачу, но там считывается из файла, а файл представляет из себя комбинацию цифр. Ни чё не понял

Автор: мисс_граффити 2.09.2007 18:28

речь про http://alglib.sources.ru/graphs/shortpathdijkstra.php?
а в чем проблема с реализацией? вроде как все подробно описано...

Автор: striker 3.09.2007 15:41

Вот исходник взял в FAQ:

UNIT Dijkstra;
Interface
Const
 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: array of integer);
Implementation
procedure Deikstr(n:integer; W:graph; u1,u2:integer;
				  var length:integer; var Weight:real; var Path: array of 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 then  
  begin
	i:=1;
	repeat
	  d[i]:=GM; p[i]:=0; m[i]:=0; i:=i+1
	until not(i<=n);
	d[u1]:=0; t:=u1;
	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;
	  repeat
		if m[i]=0 then
		begin
		  if d[i]<min then begin min:=d[i]; k:=i  end;
		end;
		i:=i+1
	  until not(i<=n);
	  if k<>0  then  begin
		m[k]:=1; t:=k;
		if t=u2 then begin length:=1; end;
	  end else begin  length:=-1 end;
	end;
	if length=1 then
	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;
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:=1 to n do for j:=1 to 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:=1 to l do write(path[i],' - ');
 readkey;
end.

А это содержимое файла, из которого считывается граф.

20
0 3 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000
3 0 10000 10000 10000 3 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000
10000 10000 0 2 10000 5 1 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000
10000 10000 2 0 3 10000 10000 5 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000
10000 10000 10000 3 0 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000
10000 3 5 10000 10000 0 10000 10000 3 10000 10000 4 10000 10000 10000 10000 10000 10000 10000 10000
10000 10000 1 10000 10000 10000 0 10000 2 2 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000
10000 10000 10000 5 10000 10000 10000 0 10000 10000 4 10000 10000 10000 10000 10000 10000 10000 10000 10000
10000 10000 10000 10000 10000 3 2 10000 0 2 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000
10000 10000 10000 10000 10000 10000 2 10000 2 0 3 10000 10000 10000 10000 10000 10000 10000 10000 10000
10000 10000 10000 10000 10000 10000 10000 4 10000 3 0 10000 4 10000 10000 5 10000 10000 10000 10000
10000 10000 10000 10000 10000 4 10000 10000 10000 10000 10000 0 4 10000 10000 10000 10000 10000 10000 10000
10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 4 4 0 4 3 10000 10000 10000 10000 10000
10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 4 0 10000 10000 3 10000 10000 10000
10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 3 10000 0 10000 10000 3 10000 10000
10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 5 10000 10000 10000 10000 0 10000 4 7 10000
10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 3 10000 10000 0 10000 10000 10000
10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 3 4 10000 0 10000 6
10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 7 10000 10000 0 10000
10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 6 10000 0


Разобрался почти во всём.
Вопрос вот в чём:
Как описывается в файле граф? Что это за числа(понимаю, что , но не знаю именно как перечисляются)
И что происходит здесь:


И здесь:
Понятно, что путь ищется, но как?

Вот граф



Эскизы прикрепленных изображений

Автор: volvo 3.09.2007 16:12

А, прости, тебе для чего ссылку на описание алгоритма привели? Чтобы опять теперь "пережевывать" то, что должно быть понятно из теоретического описания? Будь добр прочесть то, что написано в описании алгоритма (и не только на АлгЛибе, AlgoList насколько я помню, тоже содержит описание алгоритма: http://algolist.ru/maths/graphs/shortpath/dijkstra.php, да описание есть практически на любом сайте), разобраться, как оно ДОЛЖНО работать, а потом уже задавать вопросы как оно РАБОТАЕТ в какой-то определенной реализации...