Алгоритмы Дискретной математики, Нужна реализация Опции

[striker]

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

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

Сообщение отредактировано: striker - 2.09.2007 0:44

[мисс_граффити]

речь про этот алгоритм?
а в чем проблема с реализацией? вроде как все подробно описано...

[striker]

Вот исходник взял в 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


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

Код

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;

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

Вот граф


Сообщение отредактировано: striker - 3.09.2007 15:51

[volvo]

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

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