I have created a c++ function that searches for the shortest path between two points with dijkstra's shortest path algorithmus. I'm using it right now in combination with a program that solves mazes and it works quite well on up to 15K * 15K mazes (I ran short of RAM there). But I have problems solving an 2K * 2k Braid maze (one with lots of paths and loops). Tell me what I can improve.
The function itself:
bool dijkstra::GetShortestPath(std::deque<CNode> &vGraph, CNode *mStart, CNode *mEnd, std::deque<CNode*> *vPath)
{
if(mStart == 0 || mEnd == 0 || vPath == 0)
return false;
std::vector<CNode*> vUnvisited; //Priority Queue
auto mCompare = [&](CNode *lhs, CNode *rhs){return (lhs->DistanceTo > rhs->DistanceTo);};
//Set distance to start node to 0
mStart->DistanceTo = 0;
//Init Queue
vUnvisited.reserve(vGraph.size());
vUnvisited.push_back(mStart); //At the beginning the queue is empty, besides the startnode
//Dijkstra loop
{CNode *mTopNode = 0;
do{
std::pop_heap(vUnvisited.begin(), vUnvisited.end(), mCompare);
mTopNode = vUnvisited.back(); //Get nearest, not completed node
vUnvisited.pop_back(); //Remove it, it will be completed next iteration
for(auto &it : mTopNode->Connections()) //Look at all connections
{
if(it.To->DistanceTo > (mTopNode->DistanceTo + it.Distance)) //If a shorter path to a node is found, overwrite DistanceTo & PreviousNode
{
it.To->DistanceTo = (mTopNode->DistanceTo + it.Distance);
it.To->PreviousNode = mTopNode;
std::make_heap(vUnvisited.begin(), vUnvisited.end(), mCompare); //Completely sort the queue
}
if(it.To->Completed == false) //If an unvisited node has been found, add it to the queue and sort it in
{
vUnvisited.push_back(it.To->Addr());
std::push_heap(vUnvisited.begin(), vUnvisited.end(), mCompare);
}
mTopNode->Completed = true; //The current node is now completed
}
}while(!(mEnd->Completed == true || vUnvisited.size() == 0 || mTopNode->DistanceTo == std::numeric_limits<unsigned int>::max()));}
//Push path into array
{CNode *mCurrentNode;
mCurrentNode = mEnd;
while(mCurrentNode != 0)
{
vPath->push_front(mCurrentNode);
mCurrentNode = mCurrentNode->PreviousNode; //Follow the PreviousNode pointers
}}
return true;
}
The CNode class:
struct SConnection
{
SConnection(CNode *To, unsigned int Distance);
CNode *To;
unsigned int Distance;
};
class CNode
{
public:
CNode();
std::vector<SConnection> Connections()const;
bool AddConnection(CNode *mTo, unsigned int nDistance);
bool AddConnection(const SConnection &mConnection);
bool RemoveConnection(CNode *mTo);
bool operator > (const CNode &rhs)const;
bool operator < (const CNode &rhs)const;
bool operator == (const CNode &rhs)const;
CNode* Addr();
bool Completed = false;
unsigned int DistanceTo = std::numeric_limits<unsigned int>::max();
CNode *PreviousNode = 0;
unsigned int XPos = 0;
unsigned int YPos = 0;
private:
std::vector<SConnection> m_vConnections;
};
already visited list
if you had simplified the code and used a priority_queue rather than doing it manually. \$\endgroup\$