Je dois implémenter ma propre version de l'algorithme de Dijkstra basé sur les files d'attente prioritaires, et en cherchant sur certains sites à ce sujet, j'ai vu un algorithme qui fonctionne réellement mais avec d'étranges déclarations 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] && (d[j] < d[u])) //d[i] is table of distances
u = j;
QS[u] = true;
//some code
}
Je sais que ; after loop signifie que c'est une instruction vide, mais si je commente la deuxième for-loop , ce programme cesse de fonctionner, donc cela signifie en fait quelque chose. Je crois que ce u = j ++ était censé être comme le formulaire de départ u = j + 1 , mais je ne suis pas si sûr.
3 Réponses :
for (j = 0; QS [j]; j ++); est utilisé comme j = 0; while (QS [j]) j ++;
c'est-à-dire pour trouver le premier j pour lequel QS [j] est faux
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] && (d[j] < d[u])) //d[i] is table of distances
u = j;
QS[u] = true;
//some code
}
la seconde boucle for parcourt tout le tableau QS qui est un tableau de booléens. Ce qui cassera quand on est faux, enregistrant la valeur actuelle de j et démarrant la boucle suivante avec cette valeur +1.
Publiez un lien vers le site. Cette première boucle for ne fait rien.
après la boucle vide
jpointera vers le premier index deQSqui est faux.@fdan Non, ce ne sera pas le cas car le tableau pointé par QS n'est jamais initialisé, et nous avons donc UB.
@NeilButterworth il y a un commentaire qui dit "tout le QS est défini sur false ici"
eduinf.waw.pl/inf/alg/001_search/0138.php C'est en polonais donc je ne pense pas que ce serait utile