c++ - Performance of Dijkstra's algorithm implementation

Question

Below is an implementation of Dijkstra's algorithm I wrote from the pseudocode in the Wikipedia article. For a graph with about 40 000 nodes and 80 000 edges, it takes 3 or 4 minutes to run. Is that anything like the right order of magnitude? If not, what's wrong with my implementation?

struct DijkstraVertex {
  int index;
  vector<int> adj;
  vector<double> weights;
  double dist;
  int prev;
  bool opt;
  DijkstraVertex(int vertexIndex, vector<int> adjacentVertices, vector<double> edgeWeights) {
    index = vertexIndex;
    adj = adjacentVertices;
    weights = edgeWeights;
    dist = numeric_limits<double>::infinity();
    prev = -1; // "undefined" node
    opt = false; // unoptimized node
   }
};

void dijsktra(vector<DijkstraVertex*> graph, int source, vector<double> &dist, vector<int> &prev) {
  vector<DijkstraVertex*> Q(G); // set of unoptimized nodes
  G[source]->dist = 0;
  while (!Q.empty()) {
    sort(Q.begin(), Q.end(), dijkstraDistComp); // sort nodes in Q by dist from source
    DijkstraVertex* u = Q.front(); // u = node in Q with lowest dist
    u->opt = true;
    Q.erase(Q.begin());
    if (u->dist == numeric_limits<double>::infinity()) {
      break; // all remaining vertices are inaccessible from the source
    }
    for (int i = 0; i < (signed)u->adj.size(); i++) { // for each neighbour of u not in Q
    DijkstraVertex* v = G[u->adj[i]];
    if (!v->opt) {
      double alt = u->dist + u->weights[i];
      if (alt < v->dist) {
        v->dist = alt;
        v->prev = u->index;
      }
    }
    }
  }
  for (int i = 0; i < (signed)G.size(); i++) {
    assert(G[i] != NULL);
    dist.push_back(G[i]->dist); // transfer data to dist for output
    prev.push_back(G[i]->prev); // transfer data to prev for output
  }  
}

Answer 1

There are several things you can improve on this:

• implementing the priority queue with sort and erase adds a factor of |E| to the runtime - use the heap functions of the STL to get a log(N) insertion and removal into the queue.
• do not put all the nodes in the queue at once but only those where you have discovered a path (which may or may not be the optimal, as you can find an indirect path through nodes in the queue).
• creating objects for every node creates unneccessary memory fragmentation. If you care about squeezing out the last 5-10%, you could think about a solution to represent the incidence matrix and other information directly as arrays.