http://virtual-object.narod.ru
 
    Virtual Object :: Programs :: Дейкстра
  Download
 
Наша кнопка
Поиск кратчайшего пути в ориентированном графе методом Дейкстры
{$APPTYPE CONSOLE}

const unreal=987654;
var n,i,j: integer;
x,y,z: integer;
s,f: integer;
a: array [1..1000,1..1000] of integer;
d,mark: array [1..1000] of integer;
lmark: integer;
{----------------------------------------------}
function min(n:integer):integer;
var i,m:integer;
begin
 m:=maxint;
 min:=0;
 for i:=1 to n do
  if ((mark[i]=0)and(m>d[i])) then
   begin
    m:=d[i];
    min:=i;
   end;
end;
{----------------------------------------------}
procedure dist;
var u,i:integer;
begin
 for i:=1 to n do
  d[i]:=a[s,i];
 d[s]:=0;
 mark[s]:=1;
 lmark:=n-1;
 while lmark>0 do
  begin
   u:=min(n);
   mark[u]:=1;
   dec(lmark);
    for i:=1 to n do
     if (mark[i]=0) then
     if (d[i]>(d[u]+a[u,i])) then d[i]:=d[u]+a[u,i];
  end;
end;
{----------------------------------------------}
begin
 assign(input,′input.txt′); reset(input);
 assign(output,′output.txt′); rewrite(output);
 readln(n,s,f);
 for i:=1 to n do
  for j:=1 to n do
   a[i,j]:=unreal; {Левое число}
 while not(seekeof(input)) do
  begin
   readln(x,y,z);
   a[x,y]:=z;
  end;
 dist;
  if d[f]=unreal then write(′Нереально′) else writeln(d[f]);
end.
  JavaScript
  Animation
  Links
 
  Mail
 
 
 

Object © 2004 - 2005. All rights reserved.

 
Сайт создан в системе uCoz