Прошу помогите!!!!!!пропадаю....

[Allen Iverson]

Доброе время суток уважаемые программисты....
Прошу у вас помощи...

Цель задания:
Реализовать алгоритм Дейкстры для нахождения кратчайшего пути в графе между заданными парами вершин...

Язык программирования:
Turbo Prolog или Lisp...

Контакты:
e-mail: sergey_avanesov@mail.ru

Заранее спасибо...
С уважением Сергей...

[TaTT DoGG]

ооо, это очень интересная тема по математическому моделированию )) когда решаешь вручную - это довольно легко, но когда попробовал написать её... кароч на паскале она у меня есть. если найду - вышлю

[Min]

Пытался записать как можно понятнее, поэтому такая здоровая получилась:

const Inf=High(longint);
      MaxCount=100;
type
Graf=array[1..MaxCount,1..MaxCount] of integer;

Vertex=record
 way:byte;          {Сюда записывается предыдущая вершина в крат. пути}
 len:integer;       {Сюда - длинна пути от первой вершины до данной}
 enabled:boolean;   {Если true, то вершина уже просчитана}
end;

Vertexes=record
 VGraf:Graf;
 Vert:array[1..MaxCount] of Vertex;
 v:integer;         {Текущая вершина}
 Count:byte;
end;

{ Чтение Графа из Файла}
procedure ReadGrafFromFile(var inp:text;var Vert:Vertexes);
var i,j:byte;
    X:integer;
begin
 read(inp,Vert.Count);
 for i:=1 to Vert.Count do
  for j:=1 to Vert.Count do
   read(inp,Vert.VGraf[i,j]);
end;

{Подготовка к поиску (обнуление и тп)}
procedure Prepare(var Vert:Vertexes;x1:byte);
var i:byte;
begin
 for i:=1 to Vert.Count do
  begin
   Vert.Vert[i].len:=Inf;
   Vert.Vert[i].enabled:=true;
  end;
 Vert.Vert[x1].way:=0;
 Vert.Vert[x1].len:=0;
 Vert.Vert[x1].enabled:=false;
 Vert.v:=x1;
end;

{Проставляет пути для всех вершин, смежных текущей (v)}
procedure DoSmegVert(var Vert:Vertexes);
var i:byte;
begin
 for i:=1 to Vert.Count do
  begin
   if Vert.VGraf[Vert.v,i]=0 then continue;
   if (Vert.Vert[i].enabled) and (Vert.Vert[i].Len>Vert.Vert[Vert.v].Len+Vert.VGraf[Vert.v,i]) then
    begin
     Vert.Vert[i].Len:=Vert.Vert[Vert.v].Len+Vert.VGraf[Vert.v,i];
     Vert.Vert[i].way:=Vert.v;
    end;
  end;
end;

{Ищет следущую вершину. (Мин. необработанная)}
function FindNextVert(var Vert:Vertexes):boolean;
var i:byte;
    wMin:integer;
begin
 Vert.v:=-1;
 wMin:=Inf;
 for i:=1 to Vert.Count do
  if (Vert.Vert[i].enabled) and (Vert.Vert[i].Len<wMin) then
   begin
    Vert.v:=i;
    wMin:=Vert.Vert[i].Len;
   end;
 if Vert.v=-1 then FindNextVert:=false
  else
   begin
    Vert.Vert[Vert.v].enabled:=false;
    FindNextVert:=true;
   end;
end;

{Процедура поиска}
function FindWay(var Vert:Vertexes;x1,x2:byte):boolean;
var b:boolean;
begin
 Prepare(Vert,x1);
 b:=true;
 while b do
  begin
   DoSmegVert(Vert);
   b:=FindNextVert(Vert);
   if Vert.v=x2 then b:=false;
  end;
 if Vert.v=-1 then FindWay:=false
  else FindWay:=true;
end;

{Процедура возвращает путь в уже просчитанной структуре}
function GenerateWay(Vert:Vertexes;x1,x2:byte):string;
var s,sp:string;
    u:byte;
begin
 str(x2,s);
 u:=x2;
 while u<>x1 do
  begin
   str(Vert.Vert[u].way,sp);
   s:=sp+' '+s;
   u:=Vert.Vert[u].way;
  end;
 GenerateWay:=s;
end;

var x1,x2:byte;
    Vert:Vertexes;
    inp:text;
begin
 assign(inp,'input.txt');
 reset(inp);
 read(inp,x1,x2);
 ReadGrafFromFile(inp,Vert);
 if FindWay(Vert,x1,x2) then
  begin
   writeln('OK))))');
   writeln(GenerateWay(Vert,x1,x2));
  end
 else
  writeln('No Way');
 readln;
end.

[Min]

пример входного файла input.txt:
1 3
5
0 3 0 4 0
3 0 0 0 3
0 0 0 0 2
4 0 0 0 1
0 3 2 1 0

означает поиск пути от 1й до 3й вершины. Размер графа 5. И далее сам граф.

[Allen Iverson]

спасибо тебе огромное!!!!!!!!!!!!!!!!!!!!!!!!!!! !!!!!!!!!!!!!

[Allen Iverson]

может быть сможешь помочь и с вот этой?????
Написать программу, реализующую алгоритм Прима для по-строения кратчайшего остова заданного графа

заранее спасибо...

[Катерина_2000]

Сообщение от TaTT DoGG

ооо, это очень интересная тема по математическому моделированию )) когда решаешь вручную - это довольно легко, но когда попробовал написать её... кароч на паскале она у меня есть. если найду - вышлю

можно мне?

22-03-91@mail.ru

Заранее спасибо)