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.

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(min>(weight[node][k]+shortest[node])) { 
                pos = v;
                min = weight[node][k]+shortest[node];

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

  • 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, 2015 at 22:24
  • @Rufflewind since m = O(n^2), O(n^2) is correct (although rougher). Jan 26, 2015 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, 2015 at 22:53
  • @Rufflewind yeah, I know. I was referring to the formula in your comment, not to the one in the question. Jan 26, 2015 at 22:58
  • 1
    @Rufflewind but O(m + n log n) is O(n² + n log n), which is O(n²)... Jan 26, 2015 at 23:03

2 Answers 2


Now, I'm not well-versed in graph algorithms but I don't think your code implements Dijkstra's algorithm correctly. Your code as it stands will check vertices more than once, which is not what a correct implementation should do.

In Dijkstra's algorithm, one keeps track of a set of unvisited vertices so as to avoid re-checking vertices that have already been checked. Your code keeps track of a set of visited vertices, which doesn't make any sense.

  • This might be the case, but I still want to find out what the complexity of the algorithm with this implementation is. Jan 27, 2015 at 6:17
  • @DhruvMullick: your code is O(m n^2) as you said.
    – Rufflewind
    Jan 27, 2015 at 6:34

After having a similar query about Time complexity, which was cleared by JanHudec (Why does this algorithm work in O(n m)?), I now have an answer to my problem.

The time complexity should be seen from the iterations of the innermost loop. k gets incremented at most m times in every iteration of the while loop. Hence, there is an O(n m) complexity.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.