На главную Наши проекты:
Журнал   ·   Discuz!ML   ·   Wiki   ·   DRKB   ·   Помощь проекту
ПРАВИЛА FAQ Помощь Участники Календарь Избранное RSS
msm.ru
! правила раздела Алгоритмы
1. Помните, что название темы должно хоть как-то отражать ее содержимое (не создавайте темы с заголовком ПОМОГИТЕ, HELP и т.д.). Злоупотребление заглавными буквами в заголовках тем ЗАПРЕЩЕНО.
2. При создании темы постарайтесь, как можно более точно описать проблему, а не ограничиваться общими понятиями и определениями.
3. Приводимые фрагменты исходного кода старайтесь выделять тегами code.../code
4. Помните, чем подробнее Вы опишете свою проблему, тем быстрее получите вразумительный совет
5. Запрещено поднимать неактуальные темы (ПРИМЕР: запрещено отвечать на вопрос из серии "срочно надо", заданный в 2003 году)
6. И не забывайте о кнопочках TRANSLIT и РУССКАЯ КЛАВИАТУРА, если не можете писать в русской раскладке :)
Модераторы: Akina, shadeofgray
  
> Алгоритм Дейкстры
    Делал классическую задачку на Алгоритм Дейкстры:
    user posted image
    Реализовал не оптимизированую стандартную Дейстру O(N^2) точно по приведеному описанию алгоритма:
    user posted image

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

    ExpandedWrap disabled
      var
              found:boolean;
              i,j,n,k,point,min_i,temp,old_temp,sum,finish:integer;
              min:int64;
              used:array[1..100]of boolean;
              best_ways,indexes:array[1..100]of longint;
              w:array[1..100,1..100]of longint;
      begin
              assign(input,'input.txt');
              reset(input);
       
              readln(n,point,finish);
       
              for i:=1 to n do
              begin
                      for j:=1 to n do
                      begin
                              read(w[i,j]);
       
                              if(w[i,j]=-1) then
                                      w[i,j] := 100000;
                      end;
                      readln;
              end;
       
              close(input);
       
              used[point] := true;
       
              for i:=1 to n do
              begin
                      indexes[i] := point;
                      best_ways[i] := w[point,i];
              end;
       
              indexes[point] := 0;
       
              found := true;
       
              while found do
              begin
                      min := high(min);
                      found := false;
       
                      for i:=1 to n do
                              if(not used[i]) and (best_ways[i]<min) then
                              begin
                                      found := true;
                                      min := best_ways[i];
                                      min_i := i;
                              end;
       
                      if not found then
                              break;
       
                      used[min_i] := true;
       
                      for i:=1 to n do
                              if(best_ways[min_i]+w[min_i,i]<best_ways[i]) then
                              begin
                                      best_ways[i] := best_ways[min_i]+w[min_i,i];
                                      indexes[i] := min_i;
                              end;
              end;
       
              assign(output,'OUTPUT.TXT');
              rewrite(output);
       
              writeln(best_ways[finish]);
       
              close(output);
      end.


    Ах да: не надо сюда, пожалуйста, отписывать алгоритмом Дейсткстры скачаным из интернет, так как такой у меня имееться, но увы не удаеться понять то, что сам не писал.
    Сообщение отредактировано: LoLLneSS -
      Вот моя программа на паскале, работающая)
      Орграф представлен списками инцидентности.
      Pred[v] - указатель на список вершин, предыдущих для v, Sled[v] - следующих
      Ввод с клавиатуры. Вначале через пробел колво вершин и колво дуг.
      Затем через пробел начало - конец дуги. затем её вес.

      ExpandedWrap disabled
        program deikstra;
         
        CONST
          nmax=100;
          inf=1000;
        TYPE
          PT=^ZT;{указатель на запись}
          ZT=RECORD
               uzl:integer;{вершина }
               next:PT  {указатель на следующую запись}
             END;
         
        VAR
            n,m:integer; {колво вершин и дуг}
            PRED,SLED:array[1..nmax] of PT; {списки инцидентности}
            A:array[1..nmax,1..nmax] of real; {матрица весов}
            D:array[1..nmax] of real; {вектор расстояний от источника до всех вершин}
            s,t:integer; {источник, сток}
            v,u,k: integer;
            TT: array[1..nmax] of boolean; {массив рабочих вершин}
            min:real;
         
         
         PROCEDURE PUSH(var p:PT; k:integer);
         { вталкивание в стек }
         VAR p1:PT;
         begin { push }
           NEW(p1);
           p1^.uzl:=k;  p1^.next:=p;
           p:=p1;
         end; {push}
         
          FUNCTION POP(var p:PT):integer;
          { выталкивание из стека }
          var p1:PT;
          begin { pop }
            pop:=p^.UZL;
            p1:=p;
            p:=p^.next;
            dispose(p1);
          end; { pop }
         
        PROCEDURE ORSPISKI;
        {формирование списков инцидентности и матрицы весов}
        VAR i,j,u,v:integer;
        begin
          write('n, m? ');
          readln(n,m);
          for i:=1 to n do
            begin
              PRED[i]:=NIL;
              SLED[i]:=NIL;
            end;
          for i:=1 to n do
          for j:=1 to n do
              A[i,j]:=inf;
         
          for i:=1 to m do
           begin
            write('u,v? ');
            readln(u,v);
            push(PRED[v],u);
            push(SLED[u],v);
            write('A[u,v]? ');
            readln(A[u,v]);
          end;
        end;  {orspiski}
         
        PROCEDURE PRINT(s,t:integer);
        {печать пути от s до t }
        var p,stec:PT;
            u,v:integer;
         begin
           stec:=nil;
           push(stec,t);
           v:=t;
           while v<>s do
             begin
               p:=PRED[v];
               u:=p^.uzl;
               while (D[v]<>D[u]+A[u,v]) do
                begin
                  p:=p^.next;
                  u:=p^.uzl;
                end;
               push(stec,u);
               v:=u;
             end;
           while stec<>nil do
             write('<',pop(stec),'>');
         end; {print}
         
         begin {main}
          orspiski;
          write('s= ');
          readln(s);
          write('t= ');
          readln(t);
          for v:=1 to n do
            begin
              D[v]:=A[s,v];
              TT[v]:=true;
            end;
          D[s]:=0;
          TT[s]:=false;
         
          for k:=1 to n-1 do
           begin
            min:=inf; u:=0;
            for v:=1 to n do
              if TT[v] then
                if min>D[v] then
                  begin
                    min:=D[v]; u:=v
                  end;
            TT[u]:=false;
            for v:=1 to n do
              if TT[v] then
               if D[v]>D[u]+A[u,v] then
                  D[v]:=D[u]+A[u,v] ;
           end;
           for v:=1 to n do
           write(D[v]:5:2,' ');
           writeln;
           print(s,t);
           writeln;
           readln;
         end.



      Добавлено
      Описание алгоритма находится в ФАКе раздела, в файле Лекции по структурам данных
      Сообщение отредактировано: Swetlana -
        Спасибо, но уже нашол у себя ошибку. И еще:
        1. Слишал что дейкстра может работать и с отрицательными весами ребр, если нет цыклов отрицательного веса. Так ли ето?
        2. Помогите найти описание оптимизированой Дейкстры O(M log N) желательно с примером для паскаля.
        Сообщение отредактировано: LoLLneSS -
          Цитата
          1. Слишал что дейкстра может работать и с отрицательными весами ребр, если нет цыклов отрицательного веса. Так ли ето?

          НЕТ, только с неотрицательными.
          Если в орграфе есть отрицательные веса, но нет контуров отрицательного веса, то это алгоритм Форда-Беллмана.
          Если для такого графа нужна матрица расстояний (расстояния между любой парой вершин), то это алгоритм Флойда.
          0 пользователей читают эту тему (0 гостей и 0 скрытых пользователей)
          0 пользователей:


          Рейтинг@Mail.ru
          [ Script execution time: 0,0304 ]   [ 15 queries used ]   [ Generated: 29.03.24, 14:38 GMT ]