1 #ifndef __FPA__BASE__DIJKSTRA__HXX__
2 #define __FPA__BASE__DIJKSTRA__HXX__
6 // -------------------------------------------------------------------------
7 template< class V, class C, class VV, class VC, class B >
8 fpa::Base::Dijkstra< V, C, VV, VC, B >::
14 // -------------------------------------------------------------------------
15 template< class V, class C, class VV, class VC, class B >
16 fpa::Base::Dijkstra< V, C, VV, VC, B >::
21 // -------------------------------------------------------------------------
22 template< class V, class C, class VV, class VC, class B >
23 void fpa::Base::Dijkstra< V, C, VV, VC, B >::
27 typename _TNodes::const_iterator vIt = this->m_Seeds.begin( );
28 vIt != this->m_Seeds.end( );
31 this->_QueuePush( *vIt );
34 // -------------------------------------------------------------------------
35 template< class V, class C, class VV, class VC, class B >
36 bool fpa::Base::Dijkstra< V, C, VV, VC, B >::
37 _IsQueueEmpty( ) const
39 return( this->m_Queue.empty( ) );
42 // -------------------------------------------------------------------------
43 template< class V, class C, class VV, class VC, class B >
44 void fpa::Base::Dijkstra< V, C, VV, VC, B >::
45 _QueuePush( const _TNode& n )
47 this->m_Queue.push_back( n );
48 std::push_heap( this->m_Queue.begin( ), this->m_Queue.end( ) );
51 // -------------------------------------------------------------------------
52 template< class V, class C, class VV, class VC, class B >
53 typename fpa::Base::Dijkstra< V, C, VV, VC, B >::
54 _TNode fpa::Base::Dijkstra< V, C, VV, VC, B >::
58 if( !( this->m_Queue.empty( ) ) )
60 // n = *( this->m_Queue.begin( ) );
61 n = this->m_Queue.front( );
62 std::pop_heap( this->m_Queue.begin( ), this->m_Queue.end( ) );
63 this->m_Queue.pop_back( );
69 // -------------------------------------------------------------------------
70 template< class V, class C, class VV, class VC, class B >
71 void fpa::Base::Dijkstra< V, C, VV, VC, B >::
74 this->m_Queue.clear( );
77 // -------------------------------------------------------------------------
78 template< class V, class C, class VV, class VC, class B >
79 bool fpa::Base::Dijkstra< V, C, VV, VC, B >::
80 _UpdateNeigh( _TNode& nn, const _TNode& n )
82 TCost nc = this->_Cost( nn.Vertex, n.Vertex );
85 nn.Cost = n.Cost + nc;
93 #endif // __FPA__BASE__DIJKSTRA__HXX__