Блог

Мне нужно реализовать свою собственную версию алгоритма Дейкстры на основе очередей приоритетов, и при поиске на некоторых сайтах об этом я увидел алгоритм, который действительно работает, но со странными операторами for-loop:

 int i,j,n;
cin >> n;   //number of vertexes
bool *QS = new bool [n];

//whole QS is set to false here

for(i = 0; i < n; i  ) {
    for(j = 0; QS[j]; j  );
    for(u = j  ; j < n; j  )
        if(!QS[j] amp;amp; (d[j] < d[u]))   //d[i] is table of distances
            u = j;
    QS[u] = true;

    //some code
}
  

Я знаю, что ; после цикла это означает, что это пустой оператор, но если я прокомментирую второй, for-loop эта программа перестанет работать, так что это действительно что-то значит. Я считаю, что это u = j должно было быть похоже на начальную форму u = j 1 , но я не так уверен.

for(j = 0; QS[j]; j ); используется как j=0; while(QS[j])j ;

т.Е. Найти первое j, которое QS[j] равно false

 for(j = 0; QS[j]; j  );
  

устанавливает j в 0, а затем увеличивает j до тех пор, пока первый элемент в QS не станет false. Затем вы используете это значение для начального значения третьего цикла.

Это простой способ его написания, но вы можете быть намного более выразительными в отношении того, что он делает, используя std::find и std::distance подобные

 for(i = 0; i < n; i  ) {
    int j = std::distance(std::begin(QS), std::find(std::begin(QS), std::end(QS), false));
    for(u = j  ; j < n; j  )
        if(!QS[j] amp;amp; (d[j] < d[u]))   //d[i] is table of distances
            u = j;
    QS[u] = true;

    //some code
}
  

в котором явно указано, что j будет расстояние от начала массива до первого элемента false.

второй цикл for проходит через весь массив QS, который является массивом логических значений. Который прерывается, когда значение равно false, сохраняя текущее значение j и начиная следующий цикл с этого значения 1.