VPF::Алгоритмы на графах - Форум программистов

Pakshin A. S.

Дата 15.3.2007, 00:47 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Участник Клуба
Сообщений: 5056
Регистрация: 16.2.2003

Репутация: 21
Всего: 61

Взял материал: http://algolist.manual.ru/maths/graphs/shortpath/floyd.php

Попытался спрограммировать:

Код


var
  d, p, buf: array [1..5, 1..5] of integer;
  i,j: integer;
  m: integer;
  s: string;
begin
  for i:=1 to 5 do
    for j:=1 to 5 do
      begin
        p[i,j]:=i;
        if (i = j) then
          d[i,j]:=0
        else
          d[i,j]:=MaxInt;
      end;
  d[1,2]:=1;
  d[2,3]:=2;
  d[3,4]:=3;
  d[4,5]:=4;
  m:=0;
  while m < 5 do
    begin
      for i:=1 to 5 do
        for j:=1 to 5 do
          if (i <> j) then
            begin
              buf[i,j]:=Min(d[i,j], d[i, m+1] + d[m+1,j]);
              if (d[i,j] > d[i,m+1] + d[m+1,j]) then
                p[i,j]:=p[m+1,j]
            end
          else
            buf[i,j]:=0;
      d:=buf;
      inc(m)
    end;
  for i:=1 to 5 do
    begin
      s:='';
      for j:=1 to 5 do
        s:=s + IntToStr(p[i,j]) + ' ';
      Memo1.Lines.Add(s);
      s:='';
      for j:=1 to 5 do
        s:=s + IntToStr(d[i,j]) + ' ';
        Memo2.Lines.Add(s)
    end
end;

В итоге (см. обозначения по ссылке) получил:
Матрица D:

Цитата

0 1 -13 -11 -7
-15 0 -14 -12 -8
-13 -2147483648 0 -10 -6
-11 -2147483648 -10 0 -4
-7 -2147483648 -6 -4 0

Матрица P:

Цитата

1 1 1 1 1
2 2 1 1 1
2 1 3 1 1
2 1 1 4 1
2 1 1 1 5

Такое впечатление, что работает не верно... smile

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Delphi: Общие вопросы \| Следующая тема »