Поиск пути в графе, помогите найти ошибку

[spirit-ua]

Всем Привет!

Код не мой, нашел в паутине со множеством ошибок, поправил, но видемо где то все таки ошибся...

И так, есть граф:
1. нужно найти ВСЕ пути из одной точки в другую, событие кнопки Button1, это работает
2. найти КРАТЧАЙШИЙ путь, событие кнопки Button2 - работает но не правильно

Помогите найти ошибку, сам не соображаю

procedure TForm1.Button2Click(Sender: TObject);
 var
   map  :  array[1..N,1..N] of integer; // Карта map[i,j] ne 0, если точки i и j соединены
   road :  array[1..N] of integer;      // Дорога - номера точек карты
   inc1 :  array[1..N]of boolean;       // inc1[1] равен TRUE, если точка с номером i включена в road

   start,finish : integer;              // Начальная и конечная точки
   found : boolean;

   len   : integer; // длина найденного (минимального) маршрута
   c_len : integer; // длина текущего (формируемого) маршрута

   i,j : integer; // выбор очередной точки

   procedure step(s,f,p:integer);
    var
      c:integer; // Номер точки, в которую делаем очередной шаг
      i:integer;
    begin
      if s=f
        then
          begin
          //found := TRUE;
          len := c_len;  // сохраним длину найденного маршрута
          // вывод найденного маршрута
          for i:=1 to p-1 do Label1.caption:=Label1.caption+' '+IntToStr(road[i]);
          Label1.caption:=Label1.caption+', длина:'+IntToStr(len)+#13;
          end
        else
          begin
          // выбираем очередную точку
          for c:=1 to N do // проверяем все вершины
            begin
            if (map[s,c]<> 0) and (NOT inc1[c]) and ((len=0) or (c_len+map[s,c]< len)) then
              begin
              // точка соединена с текущей, но не включена в маршрут
              road[p]:=c; // добавим вершину в путь
              inc1[c]:=TRUE; // пометим вершину как включенную
              c_len:=c_len+map[s,c];
              step(c,f,p+1);
              inc1[c]:=FALSE; road[p]:=0;
              c_len:=c_len-map[s,c];
              end;
            end;
          end;
    end; // конец процедуры step

 begin

   Label1.caption := ' ';
   // инициализация массивов
   for i:=1 to N do road[i]:=0;
   for i:=1 to N do inc1[i]:=FALSE;
   // ввод описания карты из SrtingGrid.Cells
   for i:=1 to N do for j:=1 to N do
     if StringGrid1.Cells[i,j] <> ''
       then map[i,j] := StrToInt(StringGrid1.Cells[i,j])
       else map[i,j]:=0;

   start  := StrToInt(Edit1.text);
   finish := StrToInt(Edit2.text);
   len:=0; // длина найденного (минимального) маршрута с
   c_len:=0; // длина текущего (формируемого) маршрута 

   road[1]:=start;// внесем точку в маршрут
   inc1[start]:=TRUE;// пометим ее как включенную
   step(start,finish,2);//ищем вторую точку маршрута

   // проверим, найден ли хотя бы один путь
   if not found then Label1.caption:='Указанные точки не соединены!';
 end;

источник могу указать

[evg_m]

найти КРАТЧАЙШИЙ путь, событие кнопки Button2 - работает но не правильно

чтобы найти кратчайший надо сравнить ДВА и более маршрутов.

          len := c_len;  // сохраним длину найденного маршрута
          /// А где сравнение с предыдущим ?
          // и какой он предыдущий ??
                    //if c_len <len then //а этот маршрут круче
          // вывод найденного маршрута ???а вдруг будет ЕЩЕ круче
          for i:=1 to p-1 do Label1.caption:=Label1.caption+' '+IntToStr(road[i]);
          Label1.caption:=Label1.caption+', длина:'+IntToStr(len)+#13;

[spirit-ua]

Сообщение от evg_m

чтобы найти кратчайший надо сравнить ДВА и более маршрутов.

          len := c_len;  // сохраним длину найденного маршрута
          /// А где сравнение с предыдущим ?
          // и какой он предыдущий ??
                    //if c_len <len then //а этот маршрут круче
          // вывод найденного маршрута ???а вдруг будет ЕЩЕ круче
          for i:=1 to p-1 do Label1.caption:=Label1.caption+' '+IntToStr(road[i]);
          Label1.caption:=Label1.caption+', длина:'+IntToStr(len)+#13;

Получается нужно сохранять длину каждого маршрута и потом выводить самый короткий?
Так дело в том что второй "правильный" не выводит вообще

[evg_m]

Получается нужно сохранять длину каждого маршрута и потом выводить самый короткий?

Не только длину, но и сам маршрут, а иначе что же мы будем выводим.
И не всех, а только ОДИН лучший из просмотренных и менять его как только будет найден лучше.
Можно конечно всегда выводить лучший из уже проверенных (это тоже своего рода запоминание).
А еще вначале необходимо задать "самый длинный маршрут" или каким-то другим способом проверять что никакого маршрута еще нет.

поскольку обе исходные задачи (1-вывод всех; 2-вывод лучшего) подразумевают перебор всех вариантов и что-то еще
то правильный путь решения всех проблем
использовать ОДНУ и ту же процедуру перебора ПРИ решении обеих исходных задач.
Для этого она(процедура) должна уметь сообщать "вовне" о том что найден какой либо вариант(путь) и какой он есть (маршрут/длина/...)
Для сообщения удобно использовать CallBack процедуру.
В Pascal(Delphi) для этого есть процедурный тип.

type
   TCompleteStep =procedure(stepcount: integer{число шагов в маршруте}; len: integer{длина найденного маршрута}); //Вар 1

   TCompleteStepMetodform =procedure(stepcount: integer{число шагов в маршруте}; len: integer{длина найденного маршрута}) of object; //вар 2 если мы хотим чтобы наша "внешняя" процедура была бы одним из методов формы(Form1).

procedure Step(....; complete: TcompleteStep{MethodForm}); 
begin
   if c=f then Complete(....)
   else ....
end;

procedure PrintStep(stepcount: integer; len: integer); // для Вар 1
begin
  ............//печать
end;

procedure TForm1.PrintStep(stepcount: integer; len: integer); //для вар 2 //и она конечно же должна быть объявлена в TForm1 
begin
  ............//печать
end;


procedure CompareStep(stepcount: integer; len: integer);
begin
   if len<minlen then // нашли лучший 
       CopyrPath;
end;

  Step(c,f, printStep);//печать всех

  minlen:=99999999;// заведомо путь больше максимально возможного ("самый длинный маршрут") 
  step(c.f.compareStep);
  if minlen<99999999 then
    // далее печать сохраненного как лучший

[spirit-ua]

Сообщение от evg_m

поскольку обе исходные задачи (1-вывод всех; 2-вывод лучшего) подразумевают перебор всех вариантов и что-то еще
то правильный путь решения всех проблем
использовать ОДНУ и ту же процедуру перебора ПРИ решении обеих исходных задач

Я тоже так думаю и конкретном моем случае это оптимальный вариант т.к. все результаты нужно сгружать в БД, отсюда логично использовать первую процедуру поиска "всех" путей, потом сгрузить результаты в БД со всеми значениями (точка старта, промежуточные точки, конечная точка, длина маршрута и т.д.), а для второй задачи банально сделать выборку уже из БД.

Я понимаю что это не совсем "правильный" вариант решения, но чтоб реализовать вторую задачу, как я понимаю, все равно нужно просчитать все возможные варианты и выбрать оптимальный...

[evg_m]

все равно нужно просчитать все возможные варианты и выбрать оптимальный...

Да перебирать конечно нужно, но вот хранить их совсем необязательно.
получить путь, сравнить с имеющимся и если он лучше заменить имеющийся на полученный.

if A>B then A:=В;

но можно и сначала получить (и сохранить где-то) все пути а потом как-то обработать весь список.
1. вывести все пути
2. выбрать из имеющегося списка лучший.

[Poma][a]

Всегда ли мы храним только 1\0 в матрице?

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

Не совсем..

[spirit-ua]

Сообщение от Poma][a

Всегда ли мы храним только 1\0 в матрице?

Не совсем..

в данном случае да, только 1 или 0

По поводу "Не совсем.." не совсем согласен...
А если в графе не один самый "короткий" путь? тогда как?
Нужно найти не просто самый первый попавшийся короткий путь, а все самые короткие

[Serge_Bliznykov]

Сообщение от spirit-ua

По поводу "Не совсем.." не совсем согласен...
А если в графе не один самый "короткий" путь? тогда как?
Нужно найти не просто самый первый попавшийся короткий путь, а все самые короткие

ну, во-первых, такой же задачи изначально не стояло?
А во-вторых, никто не отменял динамические структуры, где и можно накапливать результаты. если есть несколько путей с одинаковой длиной, то зачем хранить миллион других, с длиной пути больше?
Чтобы, если ВДРУГ понадобится вывести самые длинные пути - опа, взять из базы?!

напоминает анекдот про мартышку, которая постоянно с собой рельсу таскала. А на вопрос - зачем, отвечала, что, мол, если лев нападёт, она рельсу бросит и легко убежит от него налегке!