C++ Dijkstra's shortest path implementation
OK this does not implement dijkstra exactly (its close).

Dijkstra looks more like this:

PriorityQueue&lt;{Node,cost}&gt;   frontierList;
List&lt;Node&gt;                   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&lt;CNode&gt; &amp;vGraph, CNode *mStart, CNode *mEnd, std::deque&lt;CNode*&gt; *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-&gt;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-&gt;DistanceTo &gt; (mTopNode-&gt;DistanceTo + it.Distance))        //If a shorter path to a node is found, overwrite DistanceTo &amp; PreviousNode
            {
                it.To-&gt;DistanceTo = (mTopNode-&gt;DistanceTo + it.Distance);
                it.To-&gt;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 -&gt;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 -&gt;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-&gt;Completed == false)       //If an unvisited node has been found, add it to the queue and sort it in
            {
                vUnvisited.push_back(it.To-&gt;Addr());
                std::push_heap(vUnvisited.begin(), vUnvisited.end(), mCompare);
            }


This line does not need to be in the loop.

            mTopNode-&gt;Completed = true;