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

[matan]

Алгоритм Дейкстры поиска кратчайшего пути на графе;программа не выводит кратчайший путь из start в finish

void main(){
   int start,finish,u;
   int dlina_puti[N];
   int put[N];
   int x[N];
   long infinity=99999999;
   printf("input start ");
   scanf("%d",&start);
   printf("input finish ");
   scanf("%d",&finish);
   for(u=0;u<N;u++){
         dlina_puti[u]=infinity;
         x[u]=0;
      }
   dlina_puti[start]=0;
   put[start]=start;
   x[start]=1;   
   int v=start;
   int w=infinity;
   while(1){
   for(u=0;u<N;u++){
         if(ports[u][v]==0) continue;
         if(dlina_puti[u]>dlina_puti[v]+ports[u][v]){
            dlina_puti[u]=dlina_puti[v]+ports[u][v];
            put[u]=v;
         }
         if(x[u]==0 && dlina_puti[u]<w){
            v=u;
            w=dlina_puti[u];
         }
      
      }
   




   if(v==finish){
      u=finish;
      while(u!=start){
         printf("%d\n",u);
         u=put[u];
      }
      printf("%d\n",dlina_puti[finish]);
      break;
   }
   x[v]=1;
   
   }
   
}

[Фома]

Ну и кто же, кроме автора будет в этом разбираться? Пройдите по-шагово в дебаггере при небольших N. Проверяйте значения промежуточных переменных (результатов).

Кроме того, подумайте, глядя, например, на строчки кода

put[start]=start;
   x[start]=1;  

Что будет с Вашей программой при start >= N?

[bekas]

Мой племянник, обучаючись в современной академии программированию, всегда говорит в случае каких-то проблем со своим ваянием: "Так она же странслировалась!?". Хотелось бы обратить внимание авторов (к примеру таких, как matan) программ на прохождение этими программами теста хотя бы на компиляцию...

[Sherpa]

такой отвратный код даже читать не хочется

[pointXY]

>>жми сюда<<
Много чего есть, в т.ч. теория и пояснения

[e2e4]

Sherpa писал(а):

такой отвратный код даже читать не хочется

А чего в нем такого отвратного?

[bekas]

Что в нем такого отвратного? Как говорится, найдите десять формальных отличий
(семантика программы сохранена, изменено только чистописание - жаль, что современным студентам-программистам не прививают нывык "чисто писать", как это делалось давным давно в первых классах школы):

void main()
{ 
   int  start, finish, u; 
   int  dlina_puti[N]; 
   int  put[N]; 
   int  x[N]; 
   int  v; 
   int  w; 
   long infinity = 99999999; 

   printf("input start "); 
   scanf("%d", &start); 
   printf("input finish "); 
   scanf("%d", &finish); 

   for(u = 0; u < N; ++u)
   { 
      dlina_puti[u] = infinity; 
      x[u]          = 0; 
   } 

   dlina_puti[start] = 0; 
   put[start]        = start; 
   x[start]          = 1;    
   v                 = start; 
   w                 = infinity; 

   for(;;)
   { 
      for(u = 0; u < N; ++u)
      { 
         if(ports[u][v] == 0)
            continue; 
         if(dlina_puti[u] > dlina_puti[v] + ports[u][v])
         { 
            dlina_puti[u] = dlina_puti[v] + ports[u][v]; 
            put[u]        = v; 
         } 
         if(x[u] == 0 && dlina_puti[u] < w)
         { 
            v = u; 
            w = dlina_puti[u]; 
         } 
      } 
    
      if(v == finish)
      { 
         for(u = finish; u != start; u = put[u])
         { 
            printf("%d\n", u); 
         } 
         printf("%d\n", dlina_puti[finish]); 
         break; 
      } 
      x[v] = 1; 
   } 
}

[вздымщик Цыпа]

bekas в сообщении #169804 писал(а):

Как говорится, найдите десять формальных отличий

Да уж красотища немерянная Позаменять везде 'while' на 'for', даже для бесконечного цикла, да повыностить открывающие фигурные скобки в отдельные строки — это несущественно для восприятия (а скобки наоборот транжирят вертикальное пространство). Понятное дело, в некоторых coding styles это обязательно, но к красоте никакого отношения не имеет. Причем, что интересно, массив с безобразным именем 'dlina_puti' и константу 'infinity' с более чем странным значением Вы не тронули

[Андрей АK]

Сразу бросилось в глаза:

         if(x[u] == 0 && dlina_puti[u] < w) 
         { 
            v = u; 
            w = dlina_puti[u]; 
         } 

При первом же обращении к этому месту w примет маленькое значение (может даже ноль) и больше это условие никогда не исполнится.
Т.е. v - так навсегда и останется случайной ближайшей к start вершиной и никогда не станет равной finish.

[e2e4]

bekas писал(а):

Что в нем такого отвратного? Как говорится, найдите десять формальных отличий
(семантика программы сохранена, изменено только чистописание - жаль, что современным студентам-программистам не прививают нывык "чисто писать", как это делалось давным давно в первых классах школы):

Овчинка выделки не стоит. Такой простой код легко читается и в том виде, как он написан у автора. А такое:

   dlina_puti[start] = 0; 
   put[start]        = start; 
   x[start]          = 1;    
   v                 = start; 
   w                 = infinity;

выглядит конечно, немерянно красиво, но это так долго набирать, что вообще-то, ИМХО, неюзабельно в принципе. Для #define это сойдет, но чтобы в тексте функции так изгаляться (он правится десятки раз) - увольте.

вздымщик Цыпа писал(а):

Причем, что интересно, массив с безобразным именем 'dlina_puti' и константу 'infinity' с более чем странным значением Вы не тронули

Наскоряк написанная функция не обязана быть оформлена по всем канонам с использованием limits.h и синтаксически правильных английских слов .

[вздымщик Цыпа]

e2e4 в сообщении #169855 писал(а):

Наскоряк написанная функция не обязана быть оформлена по всем канонам с использованием limits.h и синтаксически правильных английских слов

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

[bekas]

1.
"Причем, что интересно, массив с безобразным именем 'dlina_puti' и константу 'infinity' с более чем странным значением Вы не тронули" - и не собирался трогать, я же четко написал - правка коснулась всего лишь чистописания.

2.
"Наскоряк написанная функция не обязана быть оформлена по всем канонам с использованием limits.h и синтаксически правильных английских слов" - это мне напоминает ситуацию с человеком, который говорит, что когда наступит момент совершить подвиг, так он обязательно его сделает, а пока будет допускать мелкие прегрешения в виде перебежки улицы на красный цвет светофора - ну не поверю!

3.
"повыностить открывающие фигурные скобки в отдельные строки — это несущественно для восприятия" - ага, если не знать, что IDE Visual C++ позволяет искать парные скобки (в том числе и фигурные по Ctrl+} или Ctrl+{) - когда скобки в конце оператора - придется попрыгать по тексту

4.
"выглядит конечно, немерянно красиво, но это так долго набирать" - ага, это если не знать, что для этого надо использовать Tab.

5.
"Такой простой код легко читается и в том виде, как он написан у автора" - ага, надо при этом обладать талантом Кашперовского, чтобы сообразить, где заканчивется цикл и где его тело, когда все выравнено как в Ассемблере по одной линии - это что, делается специально, чтобы трудностей не бояться?

[вздымщик Цыпа]

bekas в сообщении #170061 писал(а):

"Наскоряк написанная функция не обязана быть оформлена по всем канонам с использованием limits.h и синтаксически правильных английских слов" - это мне напоминает ситуацию с человеком, который говорит, что когда наступит момент совершить подвиг, так он обязательно его сделает, а пока будет допускать мелкие прегрешения в виде перебежки улицы на красный цвет светофора - ну не поверю!

А имитатор перфекциониста будет строить сарай для лопат и грабель из красного дерева, тщательно шлифуя и полируя стыки, ага.

bekas в сообщении #170061 писал(а):

"повыностить открывающие фигурные скобки в отдельные строки — это несущественно для восприятия" - ага, если не знать, что IDE Visual C++ позволяет искать парные скобки (в том числе и фигурные по Ctrl+} или Ctrl+{) - когда скобки в конце оператора - придется попрыгать по тексту

Да, подстраивать стиль под специфику IDE Visual C++ — это куда как правильнее, чем выбросить его нафиг и не вспоминать об этом убожестве.

bekas в сообщении #170061 писал(а):

"выглядит конечно, немерянно красиво, но это так долго набирать" - ага, это если не знать, что для этого надо использовать Tab.

Tab в середине строки? Расстрелять.

bekas в сообщении #170061 писал(а):

"Такой простой код легко читается и в том виде, как он написан у автора" - ага, надо при этом обладать талантом Кашперовского, чтобы сообразить, где заканчивется цикл и где его тело, когда все выравнено как в Ассемблере по одной линии - это что, делается специально, чтобы трудностей не бояться?

Если кто неспособен на глаз воспринять вложенность уровня 2 без отступов в 8 позиций, то его вслед за тем, кто вставляет табы в середину строки.

И еще, Вы уже три года на форуме. Может освоите таки кнопку «вставка»?

[bekas]

IDE Visual C++ - это убожество!? Однако, батенька, вы рэвольюционэр, как говорили у нас некогда на Майдане...

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

И еще: до таких радикальных мер, как расстрелять, у нас дело не доходило, но разговоры по поводу колючей проволоки вокруг некоторых областей года четыре назад были - так что мне это не в новинку и не заставит отказаться от табуляций
(о, ужас!) в середине оператора.

[вздымщик Цыпа]

bekas в сообщении #170193 писал(а):

IDE Visual C++ - это убожество!?

Конечно. Любой IDE — убожество, а этот еще и без компилятора толком. Впрочем, на игровой консоли компайлер и не очень нужен

bekas в сообщении #170193 писал(а):

И помните: программист в первую очередь не писатель, а читатель

Вот именно. У Вас размер табуляции 4 позиции (судя по отступам), а у читателя 8 или 2. Потому, никаких пробелов в начале строк и никаких табуляций в их серединах — это важное правило.

bekas в сообщении #170193 писал(а):

разговоры по поводу колючей проволоки вокруг некоторых областей года четыре назад были

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