Listing 3: SPATH.H — Implementation of two shortest-path algorithms

/*
The predicate to the shortest-path routines must be like:

struct PRED
{
    typedef T0 value_type;
    static const value_type infinity;
    static const value_type zero;
    value_type operator()(const _ARC& arc) const;
};

value_type T0 needs (built-in types already defined):

T0 operator+(const T0& left, const T0& right);
T0 operator<(const T0& left, const T0& right);
*/

    // template struct distance_less
    //  compares second element of a pair<>
    // used by shortest_path_heap_dijkstrka
template<class _ELEM>
struct distance_less : public binary_function<_ELEM, _ELEM, bool>
{
    bool operator()(const _ELEM& x, const _ELEM& y) const
        {return x.second > y.second;}
};

    // TEMPLATE FUNCTION shortest_path WITH PRED
    // dies if there's a negative-length cycle

template<class _NET, class _NETNODEIT, class _NETNODESIZE, 
         class _Pr, class _PRTYPE> inline
bool shortest_path_heap_dijkstra(_NET& _N, _NETNODEIT _S, 
        vector<_NETNODESIZE, allocator<_NETNODESIZE> >& _pred, 
        vector<_PRTYPE, allocator<_PRTYPE> >& _dist,  _Pr& _P)
{

// body not shown ...

}
    
    // TEMPLATE FUNCTION shortest_path WITH PRED
    // returns false is a negative cycle exists in the network

template<class _NET, class _NETNODEIT, class _NETNODESIZE, 
         class _Pr, class _PRTYPE> inline
bool shortest_path_fifo_labelcorrecting(_NET& _N, _NETNODEIT _S, 
        vector<_NETNODESIZE, allocator<_NETNODESIZE> >& _pred, 
        vector<_PRTYPE, allocator<_PRTYPE> >& _dist,  _Pr& _P)
{
    typedef _PRTYPE distance_type;
    typedef _NETNODESIZE size_type;

    size_type _i, _j;
    _NET::arc_iterator ait;
    distance_type _val;

    // set initial conditions   
    int _n = _N.size_nodes();
    vector<distance_type, allocator<distance_type> > 
        _distances(_n, _Pr::infinity);
    _pred.resize(_n);
    _distances[_S - _N.begin_nodes()] = _Pr::zero;

    // _l is the list of nodes remaining to examine
    list<size_type, allocator<size_type> > _l;
    // _cnt indicates how many times we've looked at a node
    vector<int, allocator<int> > _cnt(_n, 0); 
    // _inList indicates whether a node is currently in the list
    vector<bool, allocator<bool> > _inList(_n, false);

    // put source_node into list
    _l.push_front(_S-_N.begin_nodes());
    _inList[_S-_N.begin_nodes()] = true;

    // while the list is not empty
    while( !_l.empty() )
    {
        // pull node from list to inspect
        _i = _l.front();
        // if we've looked at this node as many times as there
        // are nodes in the network, we're in a negative cycle
        if( ++(_cnt[_i]) >= _n )
            return false;   
        _l.pop_front();
        _inList[_i] = false;

        // for each arc leaving this node
        for(ait=_N.begin_arcs(_i); !(ait==_N.end_arcs(_i)); ait++)
        {
            // if distance from this node to destination is better
            // than destination's current label, then relabel
            _val = _distances[_i] + _P(*ait);
            _j = _N.arcDestinNode(ait);
            if( _val < _distances[_j] )
            {
                // relabel destination node
                _distances[_j] = _val;
                _pred[_j] = _i;
                // insert destin node in list if not already there
                if( !_inList[_j] )
                {
                    _l.push_back(_j);
                    _inList[_j] = true;
                }
            }
        }
    }
    // put outgoing distance vector into parameter provided by caller
    _dist.swap(_distances);
    return true;
}
//End of File