- template< class V, class C, class VV, class VC >
- class DijkstraTraits
- {
- public:
- typedef V TVertex;
- typedef C TResult;
- typedef C TCost;
- typedef VV TVertexValue;
- typedef VC TVertexCmp;
- typedef long TFrontId;
-
- class TNode
- {
- public:
- TNode( )
- : Cost( 0 )
- { }
- TNode( const TVertex& v, const TFrontId& f )
- : Vertex( v ),
- Parent( v ),
- Result( TResult( 0 ) ),
- FrontId( f ),
- Cost( TCost( 0 ) )
- { }
- TNode( const TVertex& v, const TResult& r, const TFrontId& f )
- : Vertex( v ),
- Parent( v ),
- Result( r ),
- FrontId( f ),
- Cost( TCost( 0 ) )
- { }
- virtual ~TNode( )
- { }
-
- // NOTE: stl::heaps work as maximum priority queues
- bool operator<( const TNode& other ) const
- { return( other.Cost < this->Cost ); }
-
- TVertex Vertex;
- TVertex Parent;
- TResult Result;
- TFrontId FrontId;
- TCost Cost;
- };
-
- typedef std::vector< TNode > TNodes;
- };
-
- /**
- * Dijkstra is a front propagation algorithm that minimizes costs
- */
- template< class V, class C, class VV, class VC, class B >