Dijkstra's Algorithm

dijkstra.hpp

#include <vector>
#include <queue>
#include <math.h>

template<typename T>
class Dijkstra
{
public:
    class GraphEdge;
    
    struct GraphVertex
    {
        friend class Dijkstra;
        T data;
        
        void addEdge(GraphVertex* vert, float score) {
            GraphEdge edge;
            edge.next = vert;
            edge.weight = score;
            edges.push_back(edge);
        }
        std::vector<GraphEdge> edges;
        
    protected:
        float score;
        bool visited = false;
    };

    struct GraphEdge
    {
        friend class Dijkstra;
        
        GraphVertex* next;
        float weight;
    };
    
    GraphVertex* createVertex ()
    {
        auto vert = new Dijkstra<T>::GraphVertex ();
        vertices.push_back(vert);
        return vert;
    }
    
    
    virtual ~Dijkstra () {
        for ( auto vert : vertices ) {
            delete vert;
        }
    }
    
    float calcPath(GraphVertex* start, GraphVertex* target, std::vector<GraphVertex*>* path)
    {
        if (start == target) return 0;
        
        // graph vertices go into a priority queue with lowest score at the top
        std::priority_queue<GraphVertex*, std::vector<GraphVertex*>, compareRange> queue;
        
        for ( auto& vertex : vertices ) {
            vertex->score = MAXFLOAT;
            vertex->visited = false;
        }
        start->score = 0;
        queue.push(start);
        
        bool found = false;
        while (!queue.empty()) {
            GraphVertex* top = queue.top();
            if (top == target) {
                found = true;
                break;
            }// break out of the loop if we have reached the target
            queue.pop();
            if (top->visited == true) continue; // skip over vertices that have alread been visited
            for ( auto& edge : top->edges ) {
                if (edge.next->visited == false) {
                    if (edge.next->score > (top->score + edge.weight)) {
                        edge.next->score = top->score + edge.weight;
                    }
                    queue.push(edge.next);
                    top->visited = true;
                }
            }
        }
        
        if (!found) return MAXFLOAT;
        
        // our graph is primed so lets get the path back to the source vertex
        
        GraphVertex* node = target;
        if (path) {
            path->push_back(node);
            while (node != start) {
                for ( auto& edge : node->edges ) {
                    if (node->score > edge.next->score) {
                        node = edge.next;
                    }
                }
                path->push_back(node);
            }
            std::reverse(path->begin(), path->end());
        }
        return target->score;
    }
    
    std::vector<GraphVertex*> vertices;
    

    struct compareRange {
        bool operator () (const GraphVertex* a, const GraphVertex* b) {
            return (a->score > b->score);
        }
    };
    
};