Раздел «Алгоритмы».DijkstraAlgoPAS:

Алгоритм Дейкстры на Pascal

//(C) Igor Kvasov
const
  maxn = 100;
  infinity = maxlongint;

var
  i,j,u,v,n,m,c,min,s,t:longint;
  e,w:array[1..maxn,1..maxn]of longint;
  ne,use,p,d:array[1..maxn]of longint;

begin
  read(n,m,t,s);
  for i:=1 to m do begin
    read(u,v,c);
    inc(ne[v]); e[v,ne[v]]:=u; //edges are inverted
    w[v,u]:=c;
  end;
  for i:=1 to n do d[i]:=infinity;
  d[s]:=0;
  for i:=1 to n do begin
    min:=infinity;
    for j:=1 to n do if (use[j]=0)and(d[j]<min) then begin
      min:=d[j]; u:=j;
    end;
    use[u]:=1;
    for j:=1 to ne[u] do begin
      v:=e[u,j];
      if d[v]>d[u]+w[u,v] then begin
        d[v]:=d[u]+w[u,v]; p[v]:=u;
      end;
    end;
  end;
  writeln(d[t]);
  u:=t; write(u);
  while u<>s do begin
    u:=p[u]; write(' ',u);
  end;
end.

-- IgorKvasov? - 28 Dec 2004

AlgorithmClasifyForm
Type: Код
Scope: Графы
Strategy:  
Complexity: Low