1

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);
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);
}
  • 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
  • 1
    @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
1

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. – Dhruv Mullick Jan 27 '15 at 6:17
  • @DhruvMullick: your code is O(m n^2) as you said. – Rufflewind Jan 27 '15 at 6:34
0

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, privacy policy and cookie policy

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