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

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;