Index: lemon/dijkstra.h
===================================================================
--- lemon/dijkstra.h	(revision 2476)
+++ lemon/dijkstra.h	(revision 2537)
@@ -24,5 +24,4 @@
 ///\brief Dijkstra algorithm.
 ///
-///\todo dijkstraZero() solution should be revised.
 
 #include <lemon/list_graph.h>
@@ -36,5 +35,43 @@
 namespace lemon {
 
-  template<class T> T dijkstraZero() {return 0;}
+  /// \brief Default OperationTraits for the Dijkstra algorithm class.
+  ///  
+  /// It defines all computational operations and constants which are
+  /// used in the Dijkstra algorithm.
+  template <typename Value>
+  struct DijkstraDefaultOperationTraits {
+    /// \brief Gives back the zero value of the type.
+    static Value zero() {
+      return static_cast<Value>(0);
+    }
+    /// \brief Gives back the sum of the given two elements.
+    static Value plus(const Value& left, const Value& right) {
+      return left + right;
+    }
+    /// \brief Gives back true only if the first value less than the second.
+    static bool less(const Value& left, const Value& right) {
+      return left < right;
+    }
+  };
+
+  /// \brief Widest path OperationTraits for the Dijkstra algorithm class.
+  ///  
+  /// It defines all computational operations and constants which are
+  /// used in the Dijkstra algorithm for widest path computation.
+  template <typename Value>
+  struct DijkstraWidestPathOperationTraits {
+    /// \brief Gives back the maximum value of the type.
+    static Value zero() {
+      return std::numeric_limits<Value>::max();
+    }
+    /// \brief Gives back the maximum of the given two elements.
+    static Value plus(const Value& left, const Value& right) {
+      return std::min(left, right);
+    }
+    /// \brief Gives back true only if the first value less than the second.
+    static bool less(const Value& left, const Value& right) {
+      return left < right;
+    }
+  };
   
   ///Default traits class of Dijkstra class.
@@ -55,5 +92,11 @@
     //The type of the length of the edges.
     typedef typename LM::Value Value;
+    /// Operation traits for Dijkstra algorithm.
+
+    /// It defines the used operation by the algorithm.
+    /// \see DijkstraDefaultOperationTraits
+    typedef DijkstraDefaultOperationTraits<Value> OperationTraits;
     /// The cross reference type used by heap.
+
 
     /// The cross reference type used by heap.
@@ -62,5 +105,5 @@
     ///Instantiates a HeapCrossRef.
 
-    ///This function instantiates a \ref HeapCrossRef. 
+    ///This function instantiates a \c HeapCrossRef. 
     /// \param G is the graph, to which we would like to define the 
     /// HeapCrossRef.
@@ -93,5 +136,5 @@
     ///Instantiates a PredMap.
  
-    ///This function instantiates a \ref PredMap. 
+    ///This function instantiates a \c PredMap. 
     ///\param G is the graph, to which we would like to define the PredMap.
     ///\todo The graph alone may be insufficient for the initialization
@@ -112,7 +155,7 @@
     ///Instantiates a ProcessedMap.
  
-    ///This function instantiates a \ref ProcessedMap. 
+    ///This function instantiates a \c ProcessedMap. 
     ///\param g is the graph, to which
-    ///we would like to define the \ref ProcessedMap
+    ///we would like to define the \c ProcessedMap
 #ifdef DOXYGEN
     static ProcessedMap *createProcessedMap(const GR &g)
@@ -171,7 +214,5 @@
 
 #ifdef DOXYGEN
-  template <typename GR,
-	    typename LM,
-	    typename TR>
+  template <typename GR, typename LM, typename TR>
 #else
   template <typename GR=ListGraph,
@@ -221,4 +262,6 @@
     ///The heap type used by the dijkstra algorithm.
     typedef typename TR::Heap Heap;
+    ///The operation traits.
+    typedef typename TR::OperationTraits OperationTraits;
   private:
     /// Pointer to the underlying graph.
@@ -404,4 +447,21 @@
       Create;
     };
+
+    template <class T>
+    struct DefOperationTraitsTraits : public Traits {
+      typedef T OperationTraits;
+    };
+    
+    /// \brief \ref named-templ-param "Named parameter" for setting 
+    /// OperationTraits type
+    ///
+    /// \ref named-templ-param "Named parameter" for setting OperationTraits
+    /// type
+    template <class T>
+    struct DefOperationTraits
+      : public Dijkstra<Graph, LengthMap, DefOperationTraitsTraits<T> > {
+      typedef Dijkstra<Graph, LengthMap, DefOperationTraitsTraits<T> >
+      Create;
+    };
     
     ///@}
@@ -550,9 +610,9 @@
     ///it is pushed to the heap only if either it was not in the heap
     ///or the shortest path found till then is shorter than \c dst.
-    void addSource(Node s,Value dst=dijkstraZero<Value>())
+    void addSource(Node s,Value dst=OperationTraits::zero())
     {
       if(_heap->state(s) != Heap::IN_HEAP) {
 	_heap->push(s,dst);
-      } else if((*_heap)[s]<dst) {
+      } else if(OperationTraits::less((*_heap)[s], dst)) {
 	_heap->set(s,dst);
 	_pred->set(s,INVALID);
@@ -578,11 +638,14 @@
 	switch(_heap->state(w)) {
 	case Heap::PRE_HEAP:
-	  _heap->push(w,oldvalue+(*length)[e]); 
+	  _heap->push(w,OperationTraits::plus(oldvalue, (*length)[e])); 
 	  _pred->set(w,e);
 	  break;
 	case Heap::IN_HEAP:
-	  if ( oldvalue+(*length)[e] < (*_heap)[w] ) {
-	    _heap->decrease(w, oldvalue+(*length)[e]); 
-	    _pred->set(w,e);
+	  {
+	    Value newvalue = OperationTraits::plus(oldvalue, (*length)[e]);
+	    if ( OperationTraits::less(newvalue, (*_heap)[w]) ) {
+	      _heap->decrease(w, newvalue); 
+	      _pred->set(w,e);
+	    }
 	  }
 	  break;
@@ -715,5 +778,5 @@
       addSource(s);
       start(t);
-      return (*_pred)[t]==INVALID?dijkstraZero<Value>():(*_dist)[t];
+      return (*_pred)[t]==INVALID?OperationTraits::zero():(*_dist)[t];
     }
     
@@ -827,4 +890,9 @@
     //The type of the length of the edges.
     typedef typename LM::Value Value;
+    /// Operation traits for Dijkstra algorithm.
+
+    /// It defines the used operation by the algorithm.
+    /// \see DijkstraDefaultOperationTraits
+    typedef DijkstraDefaultOperationTraits<Value> OperationTraits;
     ///The heap type used by Dijkstra algorithm.
 
