Implementation of Dijkstra's algorithm implementation

Question

The following is the implementation of Dijkstra's algorithm, which I wrote from the pseudocode in the Wikipedia article. A graph with approximately 40,000 nodes and 80,000 edges requires 3 or 4 minutes. Is this something like the correct order? 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 a few things you can improve about this:

• implementing a priority queue with sorting and erasing adds a factor | E | at run time - use the STL heap functions to get the attachment and deletion of the log (N) into the queue.
• Do not put all nodes in the queue at the same time, but only those where you found the path (which may or may not be optimal, since you can find an indirect path through the nodes in the queue).
• Creating objects for each node creates unnecessary memory fragmentation. If you need to compress the last 5-10%, you can think about the decision to present the incident matrix and other information directly in the form of arrays.

Answer 2

Use priority_queue.

Running My Dijkstra:

 struct edge { int v,w; edge(int _w,int _v):w(_w),v(_v){} }; vector<vector<edge> > g; enum color {white,gray,black}; vector<int> dijkstra(int s) { int n=g.size(); vector<int> d(n,-1); vector<color> c(n,white); d[s]=0; c[s]=gray; priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > q; // declare priority_queue q.push(make_pair(d[s],s)); //push starting vertex while(!q.empty()) { int u=q.top().second;q.pop(); //pop vertex from queue if(c[u]==black)continue; c[u]=black; for(int i=0;i<g[u].size();i++) { int v=g[u][i].v,w=g[u][i].w; if(c[v]==white) //new vertex found { d[v]=d[u]+w; c[v]=gray; q.push(make_pair(d[v],v)); //add vertex to queue } else if(c[v]==gray && d[v]>d[u]+w) //shorter path to gray vertex found { d[v]=d[u]+w; q.push(make_pair(d[v],v)); //push this vertex to queue } } } return d; }