1 #ifndef __FPA__BASE__DIJKSTRA__HXX__
2 #define __FPA__BASE__DIJKSTRA__HXX__
6 // -------------------------------------------------------------------------
7 template< class V, class C, class R, class S, class VC, class B >
8 fpa::Base::Dijkstra< V, C, R, S, VC, B >::
15 // -------------------------------------------------------------------------
16 template< class V, class C, class R, class S, class VC, class B >
17 fpa::Base::Dijkstra< V, C, R, S, VC, B >::
22 // -------------------------------------------------------------------------
23 template< class V, class C, class R, class S, class VC, class B >
24 bool fpa::Base::Dijkstra< V, C, R, S, VC, B >::
25 _ComputeNeighborResult(
26 TResult& result, const TVertex& neighbor, const TVertex& parent
29 result = this->_Cost( neighbor, parent );
30 result *= TResult( this->_Distance( neighbor, parent ) );
32 // WARNING: Dijkstra does not work on negative values!
33 if( result >= TResult( 0 ) )
35 _TNode pn = this->_Node( parent );
36 if( pn.Label == Self::AliveLabel && !this->m_LocalCosts )
44 // -------------------------------------------------------------------------
45 template< class V, class C, class R, class S, class VC, class B >
46 bool fpa::Base::Dijkstra< V, C, R, S, VC, B >::
47 _IsQueueEmpty( ) const
49 return( this->m_Queue.empty( ) );
52 // -------------------------------------------------------------------------
53 template< class V, class C, class R, class S, class VC, class B >
54 void fpa::Base::Dijkstra< V, C, R, S, VC, B >::
55 _QueuePush( const TVertex& v, const _TNode& n )
60 this->m_Queue.push_back( qn );
61 std::push_heap( this->m_Queue.begin( ), this->m_Queue.end( ) );
64 // -------------------------------------------------------------------------
65 template< class V, class C, class R, class S, class VC, class B >
66 void fpa::Base::Dijkstra< V, C, R, S, VC, B >::
67 _QueuePop( TVertex& v, _TNode& n )
69 _TQueueNode qn = this->m_Queue.front( );
70 std::pop_heap( this->m_Queue.begin( ), this->m_Queue.end( ) );
71 this->m_Queue.pop_back( );
76 // -------------------------------------------------------------------------
77 template< class V, class C, class R, class S, class VC, class B >
78 void fpa::Base::Dijkstra< V, C, R, S, VC, B >::
81 this->m_Queue.clear( );
84 #endif // __FPA__BASE__DIJKSTRA__HXX__