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);
}