Реализация Djikstra для больших графов


Я реализует алгоритм Djikstra для большого графа (узлов 40к, 100к дуги). Для более коротких путей searchtime под второй для более крупных (от одного конца до другого) это займет совсем несколько минут, чтобы сделать это. Я тоже рисовать путь после обыска, поэтому я использую несколько объектов Qt. Как я могу сделать это быстрее? Я чувствую, что я теряю время, когда я ищу соседей из-за структуры карты.

это класс

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

это функция поиска

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

это структура узла, он содержит карту к своим соседям с весом в качестве значения, X и y-координаты для рисования это позже, не возражаете, что

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


126
2
задан 15 апреля 2018 в 08:04 Источник Поделиться
Комментарии
1 ответ


  1. Не использование объектов Qt, когда вы не работаете с конструктов на Qt. Нет никакой выгоды для него.

  2. Ваш узел::параметр _id является беззнаковым рубашку, которая для МСВС имеет диапазон от 0 до 65535. Будьте внимательны, когда график растет.

  3. Не используйте карту. А std::vector Это способ быстрее/лучше для того, чтобы пересечь, чем std::map.

  4. Вы делаете много копирования данных:

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

Это-копия всех соседей каждый раз, когда вы получить доступ к узлу во время своего поиска. Если вам действительно нужны временные, которых вы не то, по крайней мере сделать эту ссылку.

1
ответ дан 15 апреля 2018 в 12:04 Источник Поделиться