include/Algorithms/ShortestPath/bidirectionalDijkstra.h

#ifndef BIDIRECTIONALDIJKSTRA_H
#define BIDIRECTIONALDIJKSTRA_H

#include <Structs/Trees/priorityQueue.h>


template<class GraphType>
class BidirectionalDijkstra
{
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;
    
    BidirectionalDijkstra( GraphType& graph, unsigned int* timestamp):G(graph),m_timestamp(timestamp)
    {
    }
    
        
    WeightType runQuery( const typename GraphType::NodeIterator& s, const typename GraphType::NodeIterator& t)
    {
        NodeIterator u,v,lastNode;
        EdgeIterator e,lastEdge;
        
        pqFront.clear();
        pqBack.clear();
        ++(*m_timestamp);

        minDistance = std::numeric_limits<WeightType>::max();

        s->dist = 0;
        s->timestamp = (*m_timestamp);
        s->pred = G.nilNodeDescriptor();

        t->distBack = 0;
        t->timestamp = (*m_timestamp);
        t->succ = G.nilNodeDescriptor();

        pqFront.insert( s->dist, s, &(s->pqitem));
        pqBack.insert( t->distBack, t, &(t->pqitemBack));

        while( ! ( pqFront.empty() && pqBack.empty()))
        {
            curMin = 0;
            if( !pqFront.empty()) curMin += pqFront.minKey();
            if( !pqBack.empty()) curMin += pqBack.minKey();
            if( curMin > minDistance)
            {
                break;
            }
            searchForward();
            searchBackward( s);
        }
        
        u = viaNode;
        t->dist = u->dist;
        while( u->succ != G.nilNodeDescriptor())
        {
            v = G.getNodeIterator(u->succ);
            v->pred = G.getNodeDescriptor( u);
            e = G.getEdgeIterator( u, v);
            t->dist += e->weight;
            u = v;
        }
        return t->dist;
    }   
    
private:
    GraphType& G;
    unsigned int* m_timestamp;
    PriorityQueueType pqFront, pqBack;
    NodeIterator viaNode;
    WeightType curMin, minDistance;
    
    bool isBackwardFound( const NodeIterator& u)
    {
        return (u->timestamp == (*m_timestamp)) && (u->distBack != std::numeric_limits<WeightType>::max());
    }
    
    bool isBackwardSettled( const NodeIterator& u)
    {
        return isBackwardFound(u) && (!isInBackQueue(u));
    }
    
    bool isForwardFound( const NodeIterator& u)
    {
        return (u->timestamp == (*m_timestamp)) && (u->dist != std::numeric_limits<WeightType>::max());
    }
    
    bool isForwardSettled( const NodeIterator& u)
    {
        return isForwardFound(u) && (!isInFrontQueue(u));
    }
    
    bool isInBackQueue( const NodeIterator& u)
    {
        return pqBack.contains( &(u->pqitemBack));
    }
    
    bool isInFrontQueue( const NodeIterator& u)
    {
        return pqFront.contains( &(u->pqitem));
    }
    
    void searchForward()
    {
        EdgeIterator e,lastEdge;
        NodeIterator u,v;
        if( !pqFront.empty())
        {
            u = pqFront.minItem();
            pqFront.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);
                    v->distBack = std::numeric_limits<WeightType>::max();
                    pqFront.insert( v->dist, v, &(v->pqitem));
                }
                else if( v->dist == std::numeric_limits<WeightType>::max())
                {
                    v->pred = u->getDescriptor();
                    v->dist = u->dist + e->weight;
                    pqFront.insert( v->dist, v, &(v->pqitem));
                }
                else if( v->dist > u->dist + e->weight )
                {
                    v->pred = u->getDescriptor();
                    v->dist = u->dist + e->weight;
                    pqFront.decrease( v->dist, &(v->pqitem));
                }
                
                if( isBackwardFound(v) && ( u->dist + e->weight + v->distBack < minDistance))
                {
                    minDistance = u->dist +e->weight + v->distBack;
                    //std::cout << "Settled " << G.getId(v) << " from front with " << minDistance << " (" << u->dist << "+" << v->distBack << ")!\n";
                    viaNode = v;
                }
            }
        }
    }
    
    void searchBackward( const typename GraphType::NodeIterator& s)
    {
        InEdgeIterator k,lastInEdge;
        NodeIterator u,v;
        if( !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);
                    v->dist = std::numeric_limits<WeightType>::max();
                    pqBack.insert( v->distBack, v, &(v->pqitemBack));
                }
                else if( v->distBack == std::numeric_limits<WeightType>::max())
                {
                    v->succ = u->getDescriptor();
                    v->distBack = u->distBack + k->weight;
                    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));
                }
                if( isForwardFound(v) && ( v->dist + k->weight + u->distBack < minDistance))
                {
                    minDistance = v->dist +k->weight + u->distBack;
                    //std::cout << "Settled " << G.getId(v) << " from back with " << minDistance << " (" << v->dist << "+" << u->distBack << ")!\n";
                    viaNode = v;
                }
            }
        }
    }
};

#endif//BIDIRECTIONALDIJKSTRA_H

---