C++ Graph – Why Does This Implementation of Dijkstra’s Algorithm Work in O(n^2)?

cdijkstragraph

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

Best Answer

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.

Related Topic