1 #ifndef __FPA__BASE__DIJKSTRA__HXX__
2 #define __FPA__BASE__DIJKSTRA__HXX__
6 // -------------------------------------------------------------------------
7 template< class V, class C, class R, class VC, class B >
8 fpa::Base::Dijkstra< V, C, R, VC, B >::
14 // -------------------------------------------------------------------------
15 template< class V, class C, class R, class VC, class B >
16 fpa::Base::Dijkstra< V, C, R, VC, B >::
21 // -------------------------------------------------------------------------
22 template< class V, class C, class R, class VC, class B >
23 bool fpa::Base::Dijkstra< V, C, R, VC, B >::
24 _ComputeNeighborResult(
25 TResult& result, const TVertex& neighbor, const TVertex& parent
28 result = this->_Cost( neighbor, parent );
29 result *= TResult( this->_Distance( neighbor, parent ) );
31 // WARNING: Dijkstra does not work on negative values!
32 if( result >= TResult( 0 ) )
34 _TNode pn = this->_Node( parent );
35 if( pn.Label == Self::AliveLabel )
43 // -------------------------------------------------------------------------
44 template< class V, class C, class R, class VC, class B >
45 bool fpa::Base::Dijkstra< V, C, R, VC, B >::
46 _IsQueueEmpty( ) const
48 return( this->m_Queue.empty( ) );
51 // -------------------------------------------------------------------------
52 template< class V, class C, class R, class VC, class B >
53 void fpa::Base::Dijkstra< V, C, R, VC, B >::
54 _QueuePush( const TVertex& v, const _TNode& n )
59 this->m_Queue.push_back( qn );
60 std::push_heap( this->m_Queue.begin( ), this->m_Queue.end( ) );
63 // -------------------------------------------------------------------------
64 template< class V, class C, class R, class VC, class B >
65 void fpa::Base::Dijkstra< V, C, R, VC, B >::
66 _QueuePop( TVertex& v, _TNode& n )
68 _TQueueNode qn = this->m_Queue.front( );
69 std::pop_heap( this->m_Queue.begin( ), this->m_Queue.end( ) );
70 this->m_Queue.pop_back( );
75 // -------------------------------------------------------------------------
76 template< class V, class C, class R, class VC, class B >
77 void fpa::Base::Dijkstra< V, C, R, VC, B >::
80 this->m_Queue.clear( );
83 #endif // __FPA__BASE__DIJKSTRA__HXX__