C++ Dijkstra's shortest path implementation

Question

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

• Loki Astari: Dijkstra has an already visited list (in addition to the frontier list). SO not an exact implementation of dijkstra though very dijkstra like.
• Loki Astari: This may be useful: en.cppreference.com/w/cpp/container/priority_queue
• HenrikS: Actually, std::priority_queue just uses std::make_heap internally. So it won't improve performance.
• Loki Astari: I know that. Its not about improving performance (which is the least important thing) it is about improving readability and maintainability (which is the most important thing). The amount of time developers will spend reading your code (multiple hours with many more because of the added complexity) will far exceed any performance increases you have at runtime (microseconds that may add up to a fraction of a second over a year, if it is running constantly).
• Loki Astari: Think abut how much easier it would have been to spot that you are missing the already visited list if you had simplified the code and used a priority_queue rather than doing it manually.

Answer 1

OK this does not implement dijkstra exactly (its close).

Dijkstra looks more like this:

PriorityQueue<{Node,cost}> frontierList;
List<Node> alreadyVisited;
frontierList.push({start,0});
while(!frontierList.empty())
{
 node, cost = frontierList.pop();
 if (node == end) {
 return cost;
 }
 if (alreadyVisited.find(node) != alreadyVisited.end()) {
 continue;
 }
 alreadyVisited.push(node);
 for(connect: node.connections) {
 if (alreadyVisited.find(connect.node) == alreadyVisited.end()) {
 frontierList.push({connect.node, cost + connect.cost});;
 }
 }
}
return -1; // No path found.

Notice we keep the cost in the priority list (not in the node). Otherwise you may have nodes in the list with a higher cost that need to be expunged.

You get more efficiency by using an already visited list because you don't have to expand all its connections (if you already found it then you already have the shortest path to that node).

Note: You can't put the test for alreadyUsed inside the connections loop because by the time you get to them the priority loop may have found a better way to the node.

For more details see:

• https://stackoverflow.com/a/3448361/14065
• https://stackoverflow.com/a/3765889/14065
• https://codereview.stackexchange.com/a/126688/507
• A generic implementation of Dijkstra
• https://codereview.stackexchange.com/a/103896/507
• https://codereview.stackexchange.com/a/69024/507
• https://codereview.stackexchange.com/a/77256/507

  Code Review

Passing by pointer should be avoided.

bool dijkstra::GetShortestPath(std::deque<CNode> &vGraph, CNode *mStart, CNode *mEnd, std::deque<CNode*> *vPath)
{
 if(mStart == 0 || mEnd == 0 || vPath == 0)
 return false;

If you pass these value by reference then you don't need to make this check.

This is doggy:

 //Set distance to start node to 0
 mStart->DistanceTo = 0;

It assumes that in all your nodes. You have set Completed and DistanceTo and PreviousNode to their default values. That means the algorithm is intrusive into the graph. This means the algorithm only works with this specific type of graph and can not be applied to a generic graph type.

It also assume that you go through a manual reset of the graph before you can call this function.

Don't particularly like your do {} while(); loop I think this falls more into the while() {} category.

OK this is gets a bit hard. I was sure this was broken. But as it turns out that it works fine (just inefficient).

 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
 }

Every time you encounter a path to a destination node you update the destination node with the shortest distance. But this also means you have to re-sort your whole priority queue each time you change the distance.

This is not very efficient. This is why the destination node and distance are supposed to be stored together in the priority queue (sorted by distance). Then you will always find the shortest distance to a node first. Then duplicates will be quickly removed by the Already Found List.

Checking the ->Completed flag here is an optimization that I don't have in my example (that can be added). But putting it here is not enough. You also need to check the ->completed flag before you start processing the current node mTopNode Otherwise each copy on the frontier list will push all its children on the frontier list thus growing it exponentially.

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

This line does not need to be in the loop.

 mTopNode->Completed = true;

• HenrikS: Ok, I changed my function to a "true" dijkstra algorithm. Node and cost is now seperated and make_heap is gone. The function now no longer depends on pre initialized nodes. Performance is now much better, too. Thank you for your detailed review
• Loki Astari: @HenrikS are you going to post the new version for review?
• HenrikS: Didn't plan to post it again here, but if you like, you can look up the repository of the whole program: gitlab.com/HenrikS/mazesolver