diff -r 717a5134ddeb -r 8c791ee69a45 lemon/capacity_scaling.h
--- a/lemon/capacity_scaling.h	Fri Jun 15 14:32:48 2007 +0000
+++ b/lemon/capacity_scaling.h	Fri Jun 15 14:36:24 2007 +0000
@@ -31,13 +31,15 @@
 
 #define WITH_SCALING
 
+//#define _DEBUG_ITER_
+
 namespace lemon {
 
   /// \addtogroup min_cost_flow
   /// @{
 
   /// \brief Implementation of the capacity scaling version of the
-  /// succesive shortest path algorithm for finding a minimum cost flow.
+  /// successive shortest path algorithm for finding a minimum cost flow.
   ///
   /// \ref lemon::CapacityScaling "CapacityScaling" implements a
   /// capacity scaling algorithm for finding a minimum cost flow.
@@ -299,6 +301,9 @@
     /// \brief Map for identifing deficit nodes.
     DeficitBoolMap delta_deficit;
 
+    /// \brief The deficit nodes.
+    std::vector<ResNode> deficit_nodes;
+
 #else //WITHOUT_CAPACITY_SCALING
     typedef Dijkstra<ResGraph, ReducedCostMap, ResDijkstraTraits>
       ResDijkstra;
@@ -510,9 +515,9 @@
       return c;
     }
 
-    /// \brief Runs the successive shortest path algorithm.
+    /// \brief Runs the algorithm.
     ///
-    /// Runs the successive shortest path algorithm.
+    /// Runs the algorithm.
     ///
     /// \return \c true if a feasible flow can be found.
     bool run() {
@@ -531,11 +536,13 @@
 
 #ifdef WITH_SCALING
       // Initilaizing delta value
-      Capacity max_cap = 0;
-      for (EdgeIt e(graph); e != INVALID; ++e) {
-	if (capacity[e] > max_cap) max_cap = capacity[e];
+      Supply max_sup = 0, max_dem = 0;
+      for (NodeIt n(graph); n != INVALID; ++n) {
+	if (supply[n] >  max_sup) max_sup =  supply[n];
+	if (supply[n] < -max_dem) max_dem = -supply[n];
       }
-      for (delta = 1; 2 * delta < max_cap; delta *= 2) ;
+      if (max_dem < max_sup) max_sup = max_dem;
+      for (delta = 1; 2 * delta < max_sup; delta *= 2) ;
 #endif
       return true;
     }
@@ -546,6 +553,9 @@
     bool start() {
       typedef typename DeltaResGraph::EdgeIt DeltaResEdgeIt;
       typedef typename DeltaResGraph::Edge DeltaResEdge;
+#ifdef _DEBUG_ITER_
+      int dijk_num = 0;
+#endif
 
       // Processing capacity scaling phases
       ResNode s, t;
@@ -564,18 +574,35 @@
 
 	// Finding excess nodes
 	excess_nodes.clear();
+	deficit_nodes.clear();
 	for (ResNodeIt n(res_graph); n != INVALID; ++n) {
-	  if (imbalance[n] >= delta) excess_nodes.push_back(n);
+	  if (imbalance[n] >=  delta) excess_nodes.push_back(n);
+	  if (imbalance[n] <= -delta) deficit_nodes.push_back(n);
 	}
 	next_node = 0;
 
-	// Finding successive shortest paths
+	// Finding shortest paths
 	while (next_node < excess_nodes.size()) {
+	  // Checking deficit nodes
+	  if (delta > 1) {
+	    bool delta_def = false;
+	    for (int i = 0; i < deficit_nodes.size(); ++i) {
+	      if (imbalance[deficit_nodes[i]] <= -delta) {
+		delta_def = true;
+		break;
+	      }
+	    }
+	    if (!delta_def) break;
+	  }
+
 	  // Running Dijkstra
 	  s = excess_nodes[next_node];
 	  updater.init();
 	  dijkstra.init();
 	  dijkstra.addSource(s);
+#ifdef _DEBUG_ITER_
+	  ++dijk_num;
+#endif
 	  if ((t = dijkstra.start(delta_deficit)) == INVALID) {
 	    if (delta > 1) {
 	      ++next_node;
@@ -608,6 +635,10 @@
 	  if (imbalance[s] < delta) ++next_node;
 	}
       }
+#ifdef _DEBUG_ITER_
+      std::cout << "Cost Scaling algorithm finished with running Dijkstra algorithm "
+	<< dijk_num << " times." << std::endl;
+#endif
 
       // Handling nonzero lower bounds
       if (lower) {
@@ -628,7 +659,7 @@
       if (excess_nodes.size() == 0) return true;
       next_node = 0;
 
-      // Finding successive shortest paths
+      // Finding shortest paths
       ResNode s, t;
       while ( imbalance[excess_nodes[next_node]] > 0 ||
 	      ++next_node < excess_nodes.size() )