C++ Making this Djikstra implementation faster

Question

I am implementing the Djikstra algorithm for a large graph (40k nodes, 100k arcs). For shorter paths the searchtime is under a second for larger ones (from one end to the other) it take quite some minutes to do it. I am also drawing the path after the search, so I am using some Qt objects. How could I make it faster? I feel like I am losing time when I search the neighbors because of the map structure.

this is the class

class PathFinder {
public:
   void findPath2(const Node & start, Node & finish);

   static PathFinder& getInstance();
   PathFinder();
   PathFinder(Gps gps);
   ~PathFinder();

   unsigned int* getPrev() const;
   void setPrev(unsigned int* prev);
   QVector<unsigned int> makePath(int target);

   GraphicNode* getTo();
   GraphicNode* getFrom();

   void setTo(GraphicNode* node);
   void setFrom(GraphicNode* node);

   class Compare
   {
   public:
      bool operator() (std::pair<Node*, int> a, std::pair<Node*, int> b)
      {
         return a.second > b.second;
      }
   };


private:
   static PathFinder* _pathfinder;
   Gps _gps;
   GraphicNode* _from;
   GraphicNode* _to;

   unsigned int* _prev;
   unsigned int* _dist;
   unsigned int _notVisited;

   bool selectedNode = false;


   Node* getMinNode();
   bool hasNotVisited();
};

this is the search function

void PathFinder::findPath2(const Node& start, Node& finish)
{
   QVector<Node> nodes=_gps.graph().nodes();

   std::priority_queue<std::pair<Node*,int>,std::vector<std::pair<Node*, int>>,Compare> q;

   _dist[start.id()] = 0;
   for (int i = 0; i < nodes.size(); i++) {
      std::pair<Node*, int> p = std::make_pair(const_cast<Node*>(&nodes.at(i)), _dist[i]);
      q.push(p);
   }

   while (!q.empty()) {
      std::pair<Node*, int> top = q.top();
      q.pop();
      Node* minNode = top.first;
      QMap<Node*, unsigned short> nextNodes = minNode->nextNodes();

      if (*minNode == finish) {
         return;
      }
      int minNodeId = minNode->id();
      for (QMap<Node*, unsigned short>::iterator iterator=nextNodes.begin(); iterator != nextNodes.end(); iterator++) {
         Node* nextNode = iterator.key();
         int altDist = _dist[minNodeId] + nextNodes.value(nextNode);
         int nextNodeId = nextNode->id();
         if (altDist < _dist[nextNodeId]) {
            _dist[nextNodeId] = altDist;
            _prev[nextNodeId] = minNodeId;
            std::pair<Node*, int> p = std::make_pair(nextNode, _dist[nextNodeId]);
            q.push(p);
         }
      }
   }
}

this is the structure of the node, it contains a map to its neighbors with the weight as the value, x and y are coordinates for drawing it later on, don't mind that

class Node {
private:
   unsigned short _id;
   double _y;
   double _x;
   QMap<Node*, unsigned short> _nextNodes;
   bool _visited = false;


public:
   Node();
   Node(unsigned short id, double longitude, double latitude);

   unsigned short id() const;
   double y() const;
   void setY(double y);
   double x() const;
   void setX(double x);

   bool operator==(const Node& other);
   void addNextNode(Node* node, unsigned short length);

   QMap<Node*, unsigned short> nextNodes() const;
};

Answer 1

If you're using a priority queue and an adjacency list, your implementation's complexity is O((E + V) log V). This should be more than enough to compute any shortest path in a few milliseconds on your kind of graph, on any decent CPU.

You seem to have the priority queue part done right. But why use a map instead of an adjacency list? That seems overkill.

Your implementation hides some extra, unnecessary work:

QMap<Node*, unsigned short> nextNodes = minNode->nextNodes();

This will create a copy of whatever nextNodes returns. This means that for each node, you will make a copy of all of its connected nodes, which is O(V^2) already. You might think that your QMap contains pointers to Node*, so no copying is being done. But you will copy the k pointers, one for each adjacent node, which is still bad.

You should use either a (const) reference:

const QMap<Node*, unsigned short>& nextNodes = minNode->nextNodes();

Or a pointer:

QMap<Node*, unsigned short>* nextNodes = minNode->nextNodes();

This alone should help a lot. After that, I would switch to a linked list. A QMap is implemented using a red-black tree, so iterating it will be slower than iterating a linked list.

If your graph grows a LOT more, user6106573's suggestion is very good (but completely overkill for your current graph size). Another suggestion might be to settle for a shortest path that's not exactly the shortest: https://en.wikipedia.org/wiki/A*_search_algorithm - check the Bounded relaxation section. Again, this is not needed for your current graph size.

Answer 2

If your graph never changes, a solution is to cut it into smaller graphs.

1. Calculate the shortest distance between the edges of each small graph and store the result (edge1, edge2, distance, internal shortest path).
2. When calculating the distance between 2 points, use the stored result when you reach a "small graph" edge.

I am confident that this is the kind of trick GoogleMaps and other path finder work.

The drawback is the initial cost (if your graph really never changes, you can store these "mini" shortests path a file or a database once and for all). You have to choose the size of your small graphs carefully since the accessing the stored result will have a (time) cost too (whether it is in large memory map or database). A balance must be found.

Another idea if the same path searches come back quite often is to store the most searched results.