Задача о максимальном (длиннейшем) пути в орграфе Опции

[eGEN]

Дан ориентированный граф, как в нем найти путь наибольшей длины. Вроде бы все просто, че-то я туплю. Помогите разобраться.

[Altair]

возьми алгоритм флойда, только измени следующим образом-
вместо
если путь через i и j длиннее, чем через i-k-j то сохранить k.
на
если путь через i и j короче чем через i-k-j и i-k-j не бесконечность. то сохранить k.

а бесканечность машинную можно задать как -1 например, только проверяй на бесконечность везде в арифметики.

флойд здесь:
http://forum.pascalnet.ru/index.php?s=&sh...indpost&p=40473

хотя я точно не помню, возможно такая задача решена в теории графов отдельно!

[eGEN]

Так мне же для ориентированного графа нужно, а там вроде только для неориентированного. Сможешь саму процедуру Floyd именно для орграфа написать, буду очень признателен.

[Altair]

Что за бред ? Ты граф задаешь матрицей смежности, просто у неориентированного графа она всегда симметрична

[eGEN]

С этим ясно......только я че-то не понимаю, вот Алгоритм Флойда:

Код

Const
NN=100;
Type
Graph = array[1..nn,1..nn] of longint; {граф задан матрицей смежности}
Var
n:integer;
Procedure Floyd (var a:graph; c:graph; var p:graph);
var i,j,k:integer;
begin
for i:=1 to n do
  for j:=1 to n do begin a[i,j]:=c[i,j]; p[i,j]:=0; end;
for i:=1 to n do a[i,i]:=0;
for k:=1 to n do
  for i:=1 to n do
   for j:=1 to n do
    If (a[i,k]+a[k,j]<a[i,j])  then
    begin
     a[i,j]:=a[i,k]+a[k,j];
     p[i,j]:=k;
    end;
end;

procedure ReadGraph(var a:graph);
var
i,j:integer;
begin
write('n= ');readln(n);
For i:=1 to n do for j:=1 to n do
begin write('G',i,',',j,'= ');readln(a[i,j]); end;
writeln;
end;

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;

var
a,c,p:graph;
i,j:integer;
begin
{ ReadGraph( c );}
ReadFileGraph( c );
floyd(a,c,p);
writeln('---------------------------');
for i:=1 to n do {
begin
  for j:=1 to n do write(a[i,j]:3);
writeln
end;
writeln('---------------------------');
for i:=1 to n do
begin
  for j:=1 to n do write(p[i,j]:3);
writeln
end;
readln;
end.

-----------------------------------------------------0 0 1
Для примера задаю матрицу смежности 1 0 0 и получаю:
-----------------------------------------------------0 1 0


-----------------------------------------------------------0 0 0
A- матрица содержащая кратчайшие пути = 0 0 0
-----------------------------------------------------------0 0 0


-----------------------------------------------------0 0 1
P - матрица, сохраняющая маршруты = 2 0 0
-----------------------------------------------------0 3 0

Помоему это явно не соответствует действительности, где ошибка, или я опять чего-то не понимаю?

Сообщение отредактировано: eGEN - 21.03.2006 17:38