I'm seeking a code review for the following C++ implementation of Dijkstra's algorithm. I'm trying emphasize code reusability and extensibility but performance is also potentially important.DocumentationHeap.hThis class implements the priority queue for use in Dijkstra method of Graph class. The insertion into the priority queue is performed lazily which is not a problem since the Dijkstra method inserts the initialized nodes in their priority order.The Heap<Item>  template class makes some assumptions about the stored Item API; namely that the Item object possess a .key() method. This implies that there is a coupling between Heap and Graph which is probably undesirable.The keys are stored internally to the Item class which makes it difficult to implement the decrease_key API. I have implemented a workaround which involves calling the build_min_heap method from within Graph<Label, Edge>::Dijkstra each time a node's priority is modified. This achieves log(n) complexity but is sub-optimal compared to decrease_key which requires an additional int argument locating the Node within the heap. Unfortunately each Node object does not know its own position within the heap which makes this difficult to implement. Can the Observer pattern be used here or am I overcomplicating things?Graph.hThe Graph<Label, Edge> template class contains an inner Node class. Node pointers are accessed via their Label using the pointerOf method which is implemented using std::map<Label,Node*>Each Node object contains a list outgoing edges together with their weights. I have additionally stored a list of incoming edges in order to prevent dangling pointers (see ~Node destructor).Headers#include <iostream>#include <map>#include <vector>#include <unordered_set>#include <list>Heaptemplate<class Item, class Key>class Heap {public:    // implements priority queue data ADT    void insert(Item* val);    Item* extract_min();    void build_min_heap() { for (int i = heapSize_/2 ; i >= 0 ; i--) min_heapify(i); }    int heapSize() const { return heapSize_; }private:    void decrease_key(int i, Key newkey);    void min_heapify(int i);    int parent(int i) { return i/2; }    int left(int i) { return 2*i; }    int right(int i) { return 2*i+1; }    int heapSize_ = 0;    std::vector<Item*> myHeap_;};template<class Item, class Key>void Heap<Item,Key>::decrease_key(int i, Key newkey){    if( newkey < myHeap_[i]->key() )    {        myHeap_[i]->key() = newkey;        while( i > 0 && myHeap_[parent(i)]->key() > myHeap_[i]->key() )        {            std::iter_swap( myHeap_.begin()+i,myHeap_.begin()+parent(i) );            i = parent(i);        }    }}template<class Item, class Key>void Heap<Item,Key>::insert(Item* val){    myHeap_.push_back(val);    ++heapSize_;}template<class Item, class Key>void Heap<Item,Key>::min_heapify(int i){    int l = left(i);    int r = right(i);    int smallest;    if( l < heapSize_ && myHeap_[l]->key() < myHeap_[i]->key() ) { smallest = l; }    else { smallest = i; }    if( r < heapSize_ && myHeap_[r]->key() < myHeap_[smallest]->key() ) smallest = r;    if( smallest!=i )    {        // swap i with m        std::iter_swap( myHeap_.begin()+i,myHeap_.begin()+smallest );        min_heapify(smallest);    }}template<class Item, class Key>Item* Heap<Item,Key>::extract_min(){    Item* min = myHeap_[0];    std::iter_swap(myHeap_.begin(),myHeap_.begin() + heapSize_-1);    // run min_heapify on the decremented heap    --heapSize_;    min_heapify(0);    return min;}Graphtemplate<class Label, class Edge>class Graph {public:    // adds a node to the graph    void addNode(const Label& name);    // deletes a node from the graph    void deleteNode(const Label& name);    // adds a directed edge from name1 to name2    void addEdge(const Label& name1, const Label& name2, Edge w = 1);    void listNeighbors(const Label& name);    void Dijkstra(const Label& start);private:    // forward declaration    class Node;    class CompareNode;    bool relax(Node* u, Node* v);    // returns a pointer to a node given its label    Node* pointerOf(const Label& name);    std::map<Label,Node*> nodeMap_;    // priority queue for Dijkstra    Heap<Node, Edge> Q;};template<class Label, class Edge> classGraph<Label,Edge>::Node {public:    Node(const Label& name) : label_(name), Pi_(nullptr), d_(0) {}    ~Node();    void addOutgoing(Node* p, Edge w) { outgoing_.push_back( {p,w} ); }    void addIncoming(Node* p) { incoming_.push_back(p); }    void deleteOutgoing(Node* p);    // API for priority queue    Edge key() { return d_; }    const Label& label() const { return label_; }    // node identifier    Label label_;    // incoming and outgoing nodes    std::list< std::pair<Node*, Edge> > outgoing_;    std::list<Node*> incoming_;    // predecessor/distance data structure for Dijkstra    Node* Pi_;    Edge d_;};template<class Label, class Edge>class Graph<Label,Edge>::CompareNode {public:    CompareNode(Node* n) : n_(n) {}    bool operator()(const std::pair<Node*,Edge>& elem) const { return n_ == elem.first; }private:    Node* n_;};template<class Label, class Edge>bool Graph<Label,Edge>::relax(Node* u, Node* v){    // find the weight of the node pointing from u to v    typename std::list< std::pair<Node*, Edge> >::iterator it            = std::find_if( u->outgoing_.begin(),u->outgoing_.end(),CompareNode(v) );    if( it != u->outgoing_.end() ) // if there is an edge pointing from u to v    {        Edge w = it->second;        // check relaxation condition        if(v->d_ > u->d_ + w)        {            v->d_ = u->d_ + w;            v->Pi_ = u;            return true;        }        return false;    }    return false;}template<class Label, class Edge>Graph<Label,Edge>::Node::~Node(){    // for each incoming node n, remove 'this' pointer from n's list of outgoing    for ( auto it : incoming_ ) it->deleteOutgoing(this);    std::cout << Node ' << label_ << ' destroyed\n;}template<class Label, class Edge>void Graph<Label,Edge>::addNode(const Label& name){    Node* n = new Node(name);    nodeMap_.insert( {name,n} ); // does nothing if name is already there}template<class Label, class Edge>void Graph<Label,Edge>::deleteNode(const Label& name){    typename std::map<Label,Node*>::iterator it = nodeMap_.find(name);    if( it != nodeMap_.end() ) delete it->second;}template<class Label, class Edge>void Graph<Label,Edge>::addEdge(const Label& name1,const Label& name2, Edge w){    Node* n1 = pointerOf(name1);    Node* n2 = pointerOf(name2);    if( n1 && n2 ) // if name1 and name2 exist    {        n1->addOutgoing(n2,w);        n2->addIncoming(n1);    }}template<class Label, class Edge>void Graph<Label,Edge>::listNeighbors(const Label& name){    Node* n = pointerOf(name);    for( auto it : n->outgoing_ ) std::cout << ( << it.first->label_ << , << it.second << ) <<  ;}template<class Label, class Edge>void Graph<Label,Edge>::Node::deleteOutgoing(Node* n){    typename std::list< std::pair<Node*, Edge> >::iterator it        = std::find_if(outgoing_.begin(),outgoing_.end(),CompareNode(n));    if( it != outgoing_.end() ) outgoing_.erase(it);}template<class Label, class Edge>typename Graph<Label,Edge>::Node* Graph<Label,Edge>::pointerOf(const Label& name){    typename std::map<Label,Node*>::iterator it = nodeMap_.find(name);    if( it != nodeMap_.end() ) { return it->second; }    else { return nullptr; }}template<class Label, class Edge>void Graph<Label,Edge>::Dijkstra(const Label& start){    for( auto it : Graph::nodeMap_ ) it.second->d_ = std::numeric_limits<Edge>::max();    // initialize the distance estimate of the starting node to zero    Node* pstart = pointerOf(start); // maintain pointer for future use    pstart->d_ = 0;    // create a set to store processed nodes    std::unordered_set<Node*> S;    // insert nodes into priority queue in correct order    Q.insert(pstart);    for( auto it : nodeMap_ )    {        if(it.second != pstart ) Q.insert(it.second);    }    while( Q.heapSize()!=0 ) //    {        Node* u = Q.extract_min();        S.insert( u );        // for each neighbor v of u, perform relax(u,v)        for( auto it : u->outgoing_ )        {            if( relax( u, it.first ) ) Q.build_min_heap();        }    }    // print out the shortest path weights    for( auto it : S ) std::cout << ( << it->label_ << , << it->d_ << ) <<  ;}Mainint main(){    std::vector<std::string> nodes = {a,b,c,d,e,f,g};    std::vector< std::pair<std::string,std::string> > edges =    {        {a,b},{b,c},{c,d},        {b,a},{c,b},{d,c},        {c,e},{e,f},{b,f},        {e,c},{f,e},{f,b},        {f,g},{a,g},        {g,f},{g,a}    };    std::cout << \n;    Graph<std::string,double> myGraph;    for(auto it : nodes) myGraph.addNode(it);    for(auto it : edges) myGraph.addEdge(it.first,it.second);    myGraph.Dijkstra(a);}Output(e,3) (c,2) (g,1) (d,3) (f,2) (b,1) (a,0)
Object oriented approach to Dijkstra's algorithm
c++;object oriented;graph