Almost there...

[FrontAlgorithms.git] / lib / fpa / Base / Dijkstra.hxx

diff --git a/lib/fpa/Base/Dijkstra.hxx b/lib/fpa/Base/Dijkstra.hxx
index 7d652372e1a9adbadf6171fb438967fe339f8aa0..2a2ccf5403d6ecf62b56f583e79e1d3eca807735 100644 (file)
--- a/lib/fpa/Base/Dijkstra.hxx
+++ b/lib/fpa/Base/Dijkstra.hxx
@@ -4,23 +4,23 @@
 #include <algorithm>
 
 // -------------------------------------------------------------------------
-template< class V, class C, class R, class B >
-fpa::Base::Dijkstra< V, C, R, B >::
+template< class V, class C, class R, class VC, class B >
+fpa::Base::Dijkstra< V, C, R, VC, B >::
 Dijkstra( )
   : Superclass( )
 {
 }
 
 // -------------------------------------------------------------------------
-template< class V, class C, class R, class B >
-fpa::Base::Dijkstra< V, C, R, B >::
+template< class V, class C, class R, class VC, class B >
+fpa::Base::Dijkstra< V, C, R, VC, B >::
 ~Dijkstra( )
 {
 }
 
 // -------------------------------------------------------------------------
-template< class V, class C, class R, class B >
-bool fpa::Base::Dijkstra< V, C, R, B >::
+template< class V, class C, class R, class VC, class B >
+bool fpa::Base::Dijkstra< V, C, R, VC, B >::
 _ComputeNeighborResult(
   TResult& result, const TVertex& neighbor, const TVertex& parent
   ) const
@@ -28,49 +28,53 @@ _ComputeNeighborResult(
   result  = this->_Cost( neighbor, parent );
   result *= TResult( this->_Distance( neighbor, parent ) );
 
-  _TNode pn = this->_Node( parent );
-  if( pn.Label == Self::AliveLabel )
-    result += pn.Result;
-
-  return( true );
+  // WARNING: Dijkstra does not work on negative values!
+  if( result >= TResult( 0 ) )
+  {
+    _TNode pn = this->_Node( parent );
+    if( pn.Label == Self::AliveLabel )
+      result += pn.Result;
+    return( true );
+  }
+  else
+    return( false );
 }
 
 // -------------------------------------------------------------------------
-template< class V, class C, class R, class B >
-bool fpa::Base::Dijkstra< V, C, R, B >::
+template< class V, class C, class R, class VC, class B >
+bool fpa::Base::Dijkstra< V, C, R, VC, B >::
 _IsQueueEmpty( ) const
 {
   return( this->m_Queue.empty( ) );
 }
 
 // -------------------------------------------------------------------------
-template< class V, class C, class R, class B >
-void fpa::Base::Dijkstra< V, C, R, B >::
-_QueuePush( const _TNode& n )
+template< class V, class C, class R, class VC, class B >
+void fpa::Base::Dijkstra< V, C, R, VC, B >::
+_QueuePush( const TVertex& v, const _TNode& n )
 {
-  this->m_Queue.push_back( n );
-  std::push_heap(
-    this->m_Queue.begin( ), this->m_Queue.end( ), Self::m_NodeCompare
-    );
+  _TQueueNode qn;
+  qn.Vertex = v;
+  qn.Node = n;
+  this->m_Queue.push_back( qn );
+  std::push_heap( this->m_Queue.begin( ), this->m_Queue.end( ) );
 }
 
 // -------------------------------------------------------------------------
-template< class V, class C, class R, class B >
-typename fpa::Base::Dijkstra< V, C, R, B >::
-_TNode fpa::Base::Dijkstra< V, C, R, B >::
-_QueuePop( )
+template< class V, class C, class R, class VC, class B >
+void fpa::Base::Dijkstra< V, C, R, VC, B >::
+_QueuePop( TVertex& v, _TNode& n )
 {
-  _TNode n = this->m_Queue.front( );
-  std::pop_heap(
-    this->m_Queue.begin( ), this->m_Queue.end( ), Self::m_NodeCompare
-    );
+  _TQueueNode qn = this->m_Queue.front( );
+  std::pop_heap( this->m_Queue.begin( ), this->m_Queue.end( ) );
   this->m_Queue.pop_back( );
-  return( n );
+  v = qn.Vertex;
+  n = qn.Node;
 }
 
 // -------------------------------------------------------------------------
-template< class V, class C, class R, class B >
-void fpa::Base::Dijkstra< V, C, R, B >::
+template< class V, class C, class R, class VC, class B >
+void fpa::Base::Dijkstra< V, C, R, VC, B >::
 _QueueClear( )
 {
   this->m_Queue.clear( );