trjhtr

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

1. Don't use QT objects when you are not working with QT constructs. There is no benefit to it.




2. Your node::_id is unsigned shirt, which for MSVS has a range of 0 to 65,535. Be aware of that when you graph grows.




3. Do not use a map. A std::vector is way faster/bettter for traversing than a std::map.



4. 
   

   You do a lot of copying data around:

   
   
   

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

   
   

That is a copy of all neighbors everytime you access a node during your search. If you really need the temporary, which you dont then at least make this a reference.