Perché questa implementazione dell'algoritmo di Dijkstra funziona in O (n ^ 2)?

1

Ecco il codice che uso per implementare l'algoritmo di Dijkstra. Considera un grafico con spigoli n e m . Non dovrebbe funzionare in O ( n ^ 2 m )? Qualcuno potrebbe dire che ci sono dei vertici n e che ogni spigolo viene elaborato una volta, quindi è O ( n m ). Ma il ciclo while può essere eseguito al massimo n volte, il primo al ciclo al massimo n volte e il secondo al ciclo al massimo m volte. Pertanto, questa dovrebbe essere un'implementazione O ( n ^ 2 m ).

Qui X è un vettore, la testa [] e la più corta [] sono matrici.

X.push_back(1);
head[1] = true;

while(X.size()!=MAX) {
    min = INT_MAX;

    for(j=0;j<X.size();j++) {
        node = X[j];

        for(k=0;k<graph[node].size();k++) {
            v = graph[node][k];

            if(head[v]==true)
                continue;

            if(min>(weight[node][k]+shortest[node])) { 
                pos = v;
                min = weight[node][k]+shortest[node];
            }
       }
  }

  shortest[pos] = min;
  head[pos] = true;

  X.push_back(pos);
}
    
posta Dhruv Mullick 26.01.2015 - 22:38
fonte

2 risposte

0

Dopo avere una query simile sulla complessità del tempo, che è stata cancellata da JanHudec ( Perché questo algoritmo funziona in O (nm)? ), ora ho una risposta al mio problema.

La complessità temporale dovrebbe essere vista dalle iterazioni del ciclo più interno. k viene incrementato al massimo m volte in ogni iterazione del ciclo while. Quindi, c'è una complessità O ( n m ).

    
risposta data 27.01.2015 - 12:26
fonte
1

Ora, non sono esperto in algoritmi di grafia, ma non penso che il tuo codice implementa correttamente l'algoritmo di Dijkstra. Il tuo codice in questo modo controllerà i vertici più di una volta, il che non è quello che dovrebbe fare un'implementazione corretta.

Nell'algoritmo di Dijkstra, si tiene traccia di un insieme di vertici non sorvegliati in modo da evitare di ricontrollare i vertici che sono già stati controllati. Il tuo codice tiene traccia di un insieme di vertici visitati , che non ha alcun senso.

    
risposta data 27.01.2015 - 00:23
fonte

Leggi altre domande sui tag