# Why does this implementation of Dijkstra's algorithm work in O(n^2)?

Here is the code I use for implementing Dijkstra's algorithm. Consider a graph with n vertices and m edges. Shouldn't it run in O(n^2 m) ? Someone may say that there are n vertices and each edge gets processed once, therefore it is O(n m). But the while loop can run at most n times, the 1st for loop at most n times and the second for loop at most m times. Therefore, this should be an O(n^2 m) implementation.

Here X is a vector, head[] and shortest[] are arrays.

``````X.push_back(1);

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];

continue;

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

shortest[pos] = min;

X.push_back(pos);
}
``````
• Dijkstra's algorithm is supposed to be `O(m + n log n)`, so even `O(n^2)` is more than is required. – Rufflewind Jan 26 '15 at 22:24
• @Rufflewind since `m = O(n^2)`, `O(n^2)` is correct (although rougher). – Stefano Sanfilippo Jan 26 '15 at 22:34
• @StefanoSanfilippo In the worst case scenario (a complete graph, `m = n`, so it would be `O(n^3)`. (Assuming by `m` the OP refers to edges per vertex.) – Rufflewind Jan 26 '15 at 22:53
• @Rufflewind yeah, I know. I was referring to the formula in your comment, not to the one in the question. – Stefano Sanfilippo Jan 26 '15 at 22:58
• @Rufflewind but `O(m + n log n)` is `O(n² + n log n)`, which is `O(n²)`... – Stefano Sanfilippo Jan 26 '15 at 23:03

• @DhruvMullick: your code is `O(m n^2)` as you said. – Rufflewind Jan 27 '15 at 6:34