Index: lemon/belmann_ford.h
===================================================================
--- lemon/belmann_ford.h	(revision 1723)
+++ lemon/belmann_ford.h	(revision 1741)
@@ -413,5 +413,5 @@
       int num = countNodes(*graph) - 1;
       for (int i = 0; i < num; ++i) {
-	bool ready = true;
+	bool done = true;
 	for (EdgeIt it(*graph); it != INVALID; ++it) {
 	  Node source = graph->source(it);
@@ -422,12 +422,12 @@
 	    _pred->set(target, it);
 	    _dist->set(target, relaxed);
-	    ready = false; 
+	    done = false; 
 	  }
 	}
-	if (ready) return;
-      }
-    }
-
-    /// \brief Executes the algorithm and check the negative circles.
+	if (done) return;
+      }
+    }
+
+    /// \brief Executes the algorithm and checks the negative circles.
     ///
     /// \pre init() must be called and at least one node should be added
@@ -443,5 +443,5 @@
       int num = countNodes(*graph);
       for (int i = 0; i < num; ++i) {
-	bool ready = true;
+	bool done = true;
 	for (EdgeIt it(*graph); it != INVALID; ++it) {
 	  Node source = graph->source(it);
@@ -452,8 +452,8 @@
 	    _pred->set(target, it);
 	    _dist->set(target, relaxed);
-	    ready = false; 
+	    done = false; 
 	  }
 	}
-	if (ready) return true;
+	if (done) return true;
       }
       return false;
Index: lemon/dijkstra.h
===================================================================
--- lemon/dijkstra.h	(revision 1734)
+++ lemon/dijkstra.h	(revision 1741)
@@ -62,5 +62,4 @@
     /// \param G is the graph, to which we would like to define the 
     /// HeapCrossRef.
-    /// \todo The graph alone may be insufficient for the initialization
     static HeapCrossRef *createHeapCrossRef(const GR &G) 
     {
@@ -75,6 +74,5 @@
     ///\sa Dijkstra
     typedef BinHeap<typename Graph::Node, typename LM::Value,
-		    typename GR::template NodeMap<int>,
-		    std::less<Value> > Heap;
+		    HeapCrossRef, std::less<Value> > Heap;
 
     static Heap *createHeap(HeapCrossRef& R) 
@@ -361,10 +359,10 @@
       typedef CR HeapCrossRef;
       typedef H Heap;
-      static HeapCrossRef *createHeapCrossRef(const Graph &G) {
-	return new HeapCrossRef(G);
-      }
-      static Heap *createHeap(HeapCrossRef &R) 
+      static HeapCrossRef *createHeapCrossRef(const Graph &) {
+	throw UninitializedParameter();
+      }
+      static Heap *createHeap(HeapCrossRef &) 
       {
-	return new Heap(R);
+	throw UninitializedParameter();
       }
     };
@@ -379,4 +377,30 @@
       : public Dijkstra< Graph,	LengthMap, DefHeapTraits<H, CR> > { 
       typedef Dijkstra< Graph,	LengthMap, DefHeapTraits<H, CR> > Create;
+    };
+
+    template <class H, class CR>
+    struct DefStandardHeapTraits : public Traits {
+      typedef CR HeapCrossRef;
+      typedef H Heap;
+      static HeapCrossRef *createHeapCrossRef(const Graph &G) {
+	return new HeapCrossRef(G);
+      }
+      static Heap *createHeap(HeapCrossRef &R) 
+      {
+	return new Heap(R);
+      }
+    };
+    ///\ref named-templ-param "Named parameter" for setting heap and cross 
+    ///reference type with automatic allocation
+
+    ///\ref named-templ-param "Named parameter" for setting heap and cross 
+    ///reference type. It can allocate the heap and the cross reference 
+    ///object if the cross reference's constructor waits for the graph as 
+    ///parameter and the heap's constructor waits for the cross reference.
+    template <class H, class CR = typename Graph::template NodeMap<int> >
+    struct DefStandardHeap
+      : public Dijkstra< Graph,	LengthMap, DefStandardHeapTraits<H, CR> > { 
+      typedef Dijkstra< Graph,	LengthMap, DefStandardHeapTraits<H, CR> > 
+      Create;
     };
     
@@ -454,4 +478,26 @@
       }
       _dist = &m;
+      return *this;
+    }
+
+    ///Sets the heap and the cross reference used by algorithm.
+
+    ///Sets the heap and the cross reference used by algorithm.
+    ///If you don't use this function before calling \ref run(),
+    ///it will allocate one. The destuctor deallocates this
+    ///automatically allocated map, of course.
+    ///\return <tt> (*this) </tt>
+    Dijkstra &heap(Heap& heap, HeapCrossRef &crossRef)
+    {
+      if(local_heap_cross_ref) {
+	delete _heap_cross_ref;
+	local_heap_cross_ref=false;
+      }
+      _heap_cross_ref = &crossRef;
+      if(local_heap) {
+	delete _heap;
+	local_heap=false;
+      }
+      _heap = &heap;
       return *this;
     }
Index: lemon/floyd_warshall.h
===================================================================
--- lemon/floyd_warshall.h	(revision 1723)
+++ lemon/floyd_warshall.h	(revision 1741)
@@ -393,7 +393,7 @@
 	for (NodeIt jt(*graph); jt != INVALID; ++jt) {
 	  _pred->set(it, jt, INVALID);
-	  _dist->set(it, jt, it == jt ? 
-		     OperationTraits::zero() : OperationTraits::infinity());
+	  _dist->set(it, jt, OperationTraits::infinity());
 	}
+	_dist->set(it, it, OperationTraits::zero());
       }
       for (EdgeIt it(*graph); it != INVALID; ++it) {
@@ -427,4 +427,22 @@
 	}
       }
+    }
+
+    /// \brief Executes the algorithm and checks the negative circles.
+    ///
+    /// This method runs the %FloydWarshall algorithm in order to compute 
+    /// the shortest path to each node pairs. If there is a negative circle 
+    /// in the graph it gives back false. 
+    /// The algorithm computes 
+    /// - The shortest path tree for each node.
+    /// - The distance between each node pairs.
+    bool checkedStart() {
+      start();
+      for (NodeIt it(*graph); it != INVALID; ++it) {
+	if (OperationTraits::less((*dist)(it, it), OperationTraits::zero())) {
+	  return false;
+	}
+      }
+      return true;
     }
     
Index: lemon/johnson.h
===================================================================
--- lemon/johnson.h	(revision 1723)
+++ lemon/johnson.h	(revision 1741)
@@ -107,4 +107,36 @@
     /// \see JohnsonDefaultOperationTraits
     typedef JohnsonDefaultOperationTraits<Value> OperationTraits;
+
+    /// The cross reference type used by heap.
+
+    /// The cross reference type used by heap.
+    /// Usually it is \c Graph::NodeMap<int>.
+    typedef typename Graph::template NodeMap<int> HeapCrossRef;
+
+    ///Instantiates a HeapCrossRef.
+
+    ///This function instantiates a \ref HeapCrossRef. 
+    /// \param graph is the graph, to which we would like to define the 
+    /// HeapCrossRef.
+    static HeapCrossRef *createHeapCrossRef(const Graph& graph) {
+      return new HeapCrossRef(graph);
+    }
+    
+    ///The heap type used by Dijkstra algorithm.
+
+    ///The heap type used by Dijkstra algorithm.
+    ///
+    ///\sa BinHeap
+    ///\sa Dijkstra
+    typedef BinHeap<typename Graph::Node, typename LengthMap::Value,
+		    HeapCrossRef, std::less<Value> > Heap;
+
+    ///Instantiates a Heap.
+
+    ///This function instantiates a \ref Heap. 
+    /// \param crossRef The cross reference for the heap.
+    static Heap *createHeap(HeapCrossRef& crossRef) {
+      return new Heap(crossRef);
+    }
  
     /// \brief The type of the matrix map that stores the last edges of the 
@@ -122,5 +154,5 @@
     /// \param G is the graph, to which we would like to define the PredMap.
     /// \todo The graph alone may be insufficient for the initialization
-    static PredMap *createPredMap(const _Graph& graph) {
+    static PredMap *createPredMap(const Graph& graph) {
       return new PredMap(graph);
     }
@@ -159,5 +191,7 @@
   ///
   /// The complexity of this algorithm is $O(n^2 * log(n) + n * log(n) * e)$ or
-  /// with fibonacci heap O(n^2 * log(n) + n * e).
+  /// with fibonacci heap O(n^2 * log(n) + n * e). Usually the fibonacci heap
+  /// implementation is slower than either binary heap implementation or the 
+  /// Floyd-Warshall algorithm. 
   ///
   /// The type of the length is determined by the
@@ -226,4 +260,8 @@
     /// \brief The operation traits.
     typedef typename _Traits::OperationTraits OperationTraits;
+    ///The cross reference type used for the current heap.
+    typedef typename _Traits::HeapCrossRef HeapCrossRef;
+    ///The heap type used by the dijkstra algorithm.
+    typedef typename _Traits::Heap Heap;
   private:
     /// Pointer to the underlying graph.
@@ -239,4 +277,12 @@
     ///Indicates if \ref _dist is locally allocated (\c true) or not.
     bool local_dist;
+    ///Pointer to the heap cross references.
+    HeapCrossRef *_heap_cross_ref;
+    ///Indicates if \ref _heap_cross_ref is locally allocated (\c true) or not.
+    bool local_heap_cross_ref;
+    ///Pointer to the heap.
+    Heap *_heap;
+    ///Indicates if \ref _heap is locally allocated (\c true) or not.
+    bool local_heap;
 
     /// Creates the maps if necessary.
@@ -250,7 +296,17 @@
 	_dist = Traits::createDistMap(*graph);
       }
-    }
-    
+      if (!_heap_cross_ref) {
+	local_heap_cross_ref = true;
+	_heap_cross_ref = Traits::createHeapCrossRef(*graph);
+      }
+      if (!_heap) {
+	local_heap = true;
+	_heap = Traits::createHeap(*_heap_cross_ref);
+      }
+    }
+
   public :
+
+    typedef Johnson Create;
  
     /// \name Named template parameters
@@ -309,4 +365,54 @@
       typedef Johnson< Graph, LengthMap, DefOperationTraitsTraits<T> > Create;
     };
+
+    template <class H, class CR>
+    struct DefHeapTraits : public Traits {
+      typedef CR HeapCrossRef;
+      typedef H Heap;
+      static HeapCrossRef *createHeapCrossRef(const Graph &) {
+	throw UninitializedParameter();
+      }
+      static Heap *createHeap(HeapCrossRef &) 
+      {
+	throw UninitializedParameter();
+      }
+    };
+    ///\ref named-templ-param "Named parameter" for setting heap and cross 
+    ///reference type
+
+    ///\ref named-templ-param "Named parameter" for setting heap and cross 
+    ///reference type
+    ///
+    template <class H, class CR = typename Graph::template NodeMap<int> >
+    struct DefHeap
+      : public Johnson< Graph, LengthMap, DefHeapTraits<H, CR> > { 
+      typedef Johnson< Graph, LengthMap, DefHeapTraits<H, CR> > Create;
+    };
+
+    template <class H, class CR>
+    struct DefStandardHeapTraits : public Traits {
+      typedef CR HeapCrossRef;
+      typedef H Heap;
+      static HeapCrossRef *createHeapCrossRef(const Graph &G) {
+	return new HeapCrossRef(G);
+      }
+      static Heap *createHeap(HeapCrossRef &R) 
+      {
+	return new Heap(R);
+      }
+    };
+    ///\ref named-templ-param "Named parameter" for setting heap and cross 
+    ///reference type with automatic allocation
+
+    ///\ref named-templ-param "Named parameter" for setting heap and cross 
+    ///reference type. It can allocate the heap and the cross reference 
+    ///object if the cross reference's constructor waits for the graph as 
+    ///parameter and the heap's constructor waits for the cross reference.
+    template <class H, class CR = typename Graph::template NodeMap<int> >
+    struct DefStandardHeap
+      : public Johnson< Graph, LengthMap, DefStandardHeapTraits<H, CR> > { 
+      typedef Johnson< Graph, LengthMap, DefStandardHeapTraits<H, CR> > 
+      Create;
+    };
     
     ///@}
@@ -317,4 +423,6 @@
 
   public:      
+
+    typedef Johnson Create;
     
     /// \brief Constructor.
@@ -325,10 +433,14 @@
       graph(&_graph), length(&_length),
       _pred(0), local_pred(false),
-      _dist(0), local_dist(false) {}
+      _dist(0), local_dist(false),
+      _heap_cross_ref(0), local_heap_cross_ref(false),
+      _heap(0), local_heap(false) {}
     
     ///Destructor.
     ~Johnson() {
-      if(local_pred) delete _pred;
-      if(local_dist) delete _dist;
+      if (local_pred) delete _pred;
+      if (local_dist) delete _dist;
+      if (local_heap_cross_ref) delete _heap_cross_ref;
+      if (local_heap) delete _heap;
     }
 
@@ -374,50 +486,25 @@
     }
 
-    ///\name Execution control
-    /// The simplest way to execute the algorithm is to use
-    /// one of the member functions called \c run(...).
-    /// \n
-    /// If you need more control on the execution,
-    /// Finally \ref start() will perform the actual path
-    /// computation.
-
-    ///@{
-
-    /// \brief Initializes the internal data structures.
-    /// 
-    /// Initializes the internal data structures.
-    void init() {
-      create_maps();
-    }
-    
-    /// \brief Executes the algorithm.
-    ///
-    /// This method runs the %Johnson algorithm in order to compute 
-    /// the shortest path to each node pairs. The algorithm 
-    /// computes 
-    /// - The shortest path tree for each node.
-    /// - The distance between each node pairs.
-    void start() {
-      typedef typename BelmannFord<Graph, LengthMap>::
-      template DefOperationTraits<OperationTraits>::
-      template DefPredMap<NullMap<Node, Edge> >::
-      Create BelmannFordType;
-
-      BelmannFordType belmannford(*graph, *length);
-
-      NullMap<Node, Edge> predMap;
-
-      belmannford.predMap(predMap);
+  protected:
+    
+    typedef typename BelmannFord<Graph, LengthMap>::
+    template DefOperationTraits<OperationTraits>::
+    template DefPredMap<NullMap<Node, Edge> >::
+    Create BelmannFordType;
+
+    void shiftedRun(const BelmannFordType& belmannford) {
       
-      belmannford.init(OperationTraits::zero());
-      belmannford.start();
-
+      typedef PotentialDifferenceMap<Graph, 
+      typename BelmannFordType::DistMap> PotDiffMap;
+      PotDiffMap potdiff(*graph, belmannford.distMap());
+      typedef SubMap<LengthMap, PotDiffMap> ShiftLengthMap;
+      ShiftLengthMap shiftlen(*length, potdiff);
+
+      typename Dijkstra<Graph, ShiftLengthMap>::
+      template DefHeap<Heap, HeapCrossRef>::Create dijkstra(*graph, shiftlen);
+
+      dijkstra.heap(*_heap, *_heap_cross_ref);
+      
       for (NodeIt it(*graph); it != INVALID; ++it) {
-	typedef PotentialDifferenceMap<Graph, 
-	  typename BelmannFordType::DistMap> PotDiffMap;
-	PotDiffMap potdiff(*graph, belmannford.distMap());
-	typedef SubMap<LengthMap, PotDiffMap> ShiftLengthMap;
-	ShiftLengthMap shiftlen(*length, potdiff);
-	Dijkstra<Graph, ShiftLengthMap> dijkstra(*graph, shiftlen); 
 	dijkstra.run(it);
 	for (NodeIt jt(*graph); jt != INVALID; ++jt) {
@@ -433,4 +520,68 @@
       }
     }
+
+  public:    
+
+    ///\name Execution control
+    /// The simplest way to execute the algorithm is to use
+    /// one of the member functions called \c run(...).
+    /// \n
+    /// If you need more control on the execution,
+    /// Finally \ref start() will perform the actual path
+    /// computation.
+
+    ///@{
+
+    /// \brief Initializes the internal data structures.
+    /// 
+    /// Initializes the internal data structures.
+    void init() {
+      create_maps();
+    }
+
+    /// \brief Executes the algorithm.
+    ///
+    /// This method runs the %Johnson algorithm in order to compute 
+    /// the shortest path to each node pairs. The algorithm 
+    /// computes 
+    /// - The shortest path tree for each node.
+    /// - The distance between each node pairs.
+    void start() {
+
+      BelmannFordType belmannford(*graph, *length);
+
+      NullMap<Node, Edge> predMap;
+
+      belmannford.predMap(predMap);
+      
+      belmannford.init(OperationTraits::zero());
+      belmannford.start();
+
+      shiftedRun(belmannford);
+    }
+
+    /// \brief Executes the algorithm and checks the negatvie circles.
+    ///
+    /// This method runs the %Johnson algorithm in order to compute 
+    /// the shortest path to each node pairs. If the graph contains
+    /// negative circle it gives back false. The algorithm 
+    /// computes 
+    /// - The shortest path tree for each node.
+    /// - The distance between each node pairs.
+    bool checkedStart() {
+
+      BelmannFordType belmannford(*graph, *length);
+
+      NullMap<Node, Edge> predMap;
+
+      belmannford.predMap(predMap);
+      
+      belmannford.init(OperationTraits::zero());
+      if (!belmannford.checkedStart()) return false;
+
+      shiftedRun(belmannford);
+      return true;
+    }
+
     
     /// \brief Runs %Johnson algorithm.
