include/Algorithms/ShortestPath/dijkstra.h

#ifndef DIJKSTRA_H
#define DIJKSTRA_H

#include <Structs/Trees/priorityQueue.h>


template<class GraphType>
class Dijkstra
{
public:
    typedef typename GraphType::NodeIterator                        NodeIterator;
    typedef typename GraphType::EdgeIterator                        EdgeIterator;
    typedef typename GraphType::SizeType                            SizeType;
    typedef unsigned int                                            WeightType;
    typedef PriorityQueue< WeightType, NodeIterator, HeapStorage>   PriorityQueueType;
    
    Dijkstra( GraphType& graph, unsigned int* timestamp):G(graph),m_timestamp(timestamp)
    {
    }
    
    void buildTree( const typename GraphType::NodeIterator& s)
    {
        NodeIterator u,v,lastNode;
        EdgeIterator e,lastEdge;
        
        pq.clear();
        ++(*m_timestamp);
        s->dist = 0;
        s->timestamp = (*m_timestamp);
        s->pred = G.nilNodeDescriptor();

        pq.insert( s->dist, s, &(s->pqitem));

        while( !pq.empty())
        {
            u = pq.minItem();
            pq.popMin();

            for( e = G.beginEdges(u), lastEdge = G.endEdges(u); e != lastEdge; ++e)
            {
                v = G.target(e);

                if( v->timestamp < (*m_timestamp))
                {
                    v->pred = u->getDescriptor();
                    v->dist = u->dist + e->weight;
                    v->timestamp = (*m_timestamp);
                    pq.insert( v->dist, v, &(v->pqitem));
                }
                else if( v->dist > u->dist + e->weight )
                {
                    v->pred = u->getDescriptor();
                    v->dist = u->dist + e->weight;
                    pq.decrease( v->dist, &(v->pqitem));
                }
            }
        }
    }
    
    WeightType runQuery( const typename GraphType::NodeIterator& s, const typename GraphType::NodeIterator& t)
    {
        NodeIterator u,v,lastNode;
        EdgeIterator e,lastEdge;
        
        pq.clear();
        ++(*m_timestamp);
        s->dist = 0;
        s->timestamp = (*m_timestamp);
        s->pred = G.nilNodeDescriptor();;

        pq.insert( s->dist, s, &(s->pqitem));

        while( !pq.empty())
        {
            u = pq.minItem();
            pq.popMin();
            if( u == t) break;
            for( e = G.beginEdges(u), lastEdge = G.endEdges(u); e != lastEdge; ++e)
            {
                v = G.target(e);

                if( v->timestamp < (*m_timestamp))
                {
                    v->pred = u->getDescriptor();
                    v->dist = u->dist + e->weight;
                    v->timestamp = (*m_timestamp);
                    pq.insert( v->dist, v, &(v->pqitem));
                }
                else if( v->dist > u->dist + e->weight )
                {
                    v->pred = u->getDescriptor();
                    v->dist = u->dist + e->weight;
                    pq.decrease( v->dist, &(v->pqitem));
                }
            }
        }
        return t->dist;
    }
    
private:
    GraphType& G;
    unsigned int* m_timestamp;
    PriorityQueueType pq;
};



template<class GraphType>
class BackwardDijkstra
{
public:
    typedef typename GraphType::NodeIterator                        NodeIterator;
    typedef typename GraphType::NodeDescriptor                      NodeDescriptor;
    typedef typename GraphType::EdgeIterator                        EdgeIterator;
    typedef typename GraphType::InEdgeIterator                    InEdgeIterator;
    typedef typename GraphType::SizeType                            SizeType;
    typedef unsigned int                                            WeightType;
    typedef PriorityQueue< WeightType, NodeIterator, HeapStorage>   PriorityQueueType;
    
    BackwardDijkstra( GraphType& graph, unsigned int* timestamp):G(graph),m_timestamp(timestamp)
    {
    }
    
    void buildTree( const typename GraphType::NodeIterator& t)
    {
        NodeIterator u,v,lastNode;
        InEdgeIterator k,lastInEdge;
        
        pqBack.clear();
        ++(*m_timestamp);
        t->distBack = 0;
        t->timestamp = (*m_timestamp);
        t->succ = G.nilNodeDescriptor();;

        pqBack.insert( t->distBack, t, &(t->pqitemBack));

        while( !pqBack.empty())
        {
            u = pqBack.minItem();
            pqBack.popMin();
            for( k = G.beginInEdges(u), lastInEdge = G.endInEdges(u); k != lastInEdge; ++k)
            {
                v = G.source(k);

                if( v->timestamp < (*m_timestamp))
                {
                    v->succ = u->getDescriptor();
                    v->distBack = u->distBack + k->weight;
                    v->timestamp = (*m_timestamp);
                    pqBack.insert( v->distBack, v, &(v->pqitemBack));
                }
                else if( v->distBack > u->distBack + k->weight )
                {
                    v->succ = u->getDescriptor();
                    v->distBack = u->distBack + k->weight;
                    pqBack.decrease( v->distBack, &(v->pqitemBack));
                }
            }
        }
    }
    
    WeightType runQuery( const typename GraphType::NodeIterator& s, const typename GraphType::NodeIterator& t)
    {
        NodeIterator u,v,lastNode;
        InEdgeIterator k,lastInEdge;
        
        pqBack.clear();
        ++(*m_timestamp);
        t->distBack = 0;
        t->timestamp = (*m_timestamp);
        t->succ = G.nilNodeDescriptor();;

        pqBack.insert( t->distBack, t, &(t->pqitemBack));

        while( !pqBack.empty())
        {
            u = pqBack.minItem();
            pqBack.popMin();
            if( u == s) break;
            for( k = G.beginInEdges(u), lastInEdge = G.endInEdges(u); k != lastInEdge; ++k)
            {
                v = G.source(k);

                if( v->timestamp < (*m_timestamp))
                {
                    v->succ = u->getDescriptor();
                    v->distBack = u->distBack + k->weight;
                    v->timestamp = (*m_timestamp);
                    pqBack.insert( v->distBack, v, &(v->pqitemBack));
                }
                else if( v->distBack > u->distBack + k->weight )
                {
                    v->succ = u->getDescriptor();
                    v->distBack = u->distBack + k->weight;
                    pqBack.decrease( v->distBack, &(v->pqitemBack));
                }
            }
        }
        
        u = s;
        t->dist = 0;
        EdgeIterator e;
        while( u->succ != G.nilNodeDescriptor())
        {
            v = G.getNodeIterator( u->succ);
            e = G.getEdgeIterator( u, v);
            t->dist += e->weight;
            v->pred = G.getNodeDescriptor(u);
            u = v;
        }
        return t->dist;
    }
    
private:
    GraphType& G;
    unsigned int* m_timestamp;
    PriorityQueueType pqBack;
};

#endif//DIJKSTRA_H

---