Index: lemon/belmann_ford.h
===================================================================
 lemon/belmann_ford.h (revision 1710)
+++ lemon/belmann_ford.h (revision 1723)
@@ 145,8 +145,16 @@
///
/// \ingroup flowalgs
 /// This class provides an efficient implementation of \c BelmannFord
+ /// This class provides an efficient implementation of \c BelmannFord
/// algorithm. The edge lengths are passed to the algorithm using a
/// \ref concept::ReadMap "ReadMap", so it is easy to change it to any
/// kind of length.
+ ///
+ /// The BelmannFord algorithm solves the shortest path from one node
+ /// problem when the edges can have negative length but the graph should
+ /// not contain circle with negative sum of length. If we can assume
+ /// that all edge is nonnegative in the graph then the dijkstra algorithm
+ /// should be used rather.
+ ///
+ /// The complexity of the algorithm is O(n * e).
///
/// The type of the length is determined by the
@@ 403,7 +411,7 @@
///  The distance of each node from the root(s).
void start() {
 bool ready = false;
 while (!ready) {
 ready = true;
+ int num = countNodes(*graph)  1;
+ for (int i = 0; i < num; ++i) {
+ bool ready = true;
for (EdgeIt it(*graph); it != INVALID; ++it) {
Node source = graph>source(it);
@@ 417,5 +425,37 @@
}
}
 }
+ if (ready) return;
+ }
+ }
+
+ /// \brief Executes the algorithm and check the negative circles.
+ ///
+ /// \pre init() must be called and at least one node should be added
+ /// with addSource() before using this function. If there is
+ /// a negative circle in the graph it gives back false.
+ ///
+ /// This method runs the %BelmannFord algorithm from the root node(s)
+ /// in order to compute the shortest path to each node. The algorithm
+ /// computes
+ ///  The shortest path tree.
+ ///  The distance of each node from the root(s).
+ bool checkedStart() {
+ int num = countNodes(*graph);
+ for (int i = 0; i < num; ++i) {
+ bool ready = true;
+ for (EdgeIt it(*graph); it != INVALID; ++it) {
+ Node source = graph>source(it);
+ Node target = graph>target(it);
+ Value relaxed =
+ OperationTraits::plus((*_dist)[source], (*length)[it]);
+ if (OperationTraits::less(relaxed, (*_dist)[target])) {
+ _pred>set(target, it);
+ _dist>set(target, relaxed);
+ ready = false;
+ }
+ }
+ if (ready) return true;
+ }
+ return false;
}
Index: lemon/floyd_warshall.h
===================================================================
 lemon/floyd_warshall.h (revision 1710)
+++ lemon/floyd_warshall.h (revision 1723)
@@ 28,4 +28,5 @@
#include
#include
+#include
#include
@@ 106,12 +107,12 @@
typedef FloydWarshallDefaultOperationTraits OperationTraits;
 /// \brief The type of the map that stores the last edges of the
+ /// \brief The type of the matrix map that stores the last edges of the
/// shortest paths.
///
 /// The type of the map that stores the last
 /// edges of the shortest paths.
+ /// The type of the map that stores the last edges of the shortest paths.
/// It must be a matrix map with \c Graph::Edge value type.
///
 typedef NodeMatrixMap PredMap;
+ typedef DynamicMatrixMap PredMap;
/// \brief Instantiates a PredMap.
@@ 127,7 +128,7 @@
///
/// The type of the map that stores the dists of the nodes.
 /// It must meet the \ref concept::WriteMap "WriteMap" concept.
 ///
 typedef NodeMatrixMap DistMap;
+ /// It must meet the \ref concept::WriteMatrixMap "WriteMatrixMap" concept.
+ ///
+ typedef DynamicMatrixMap DistMap;
/// \brief Instantiates a DistMap.
@@ 149,4 +150,13 @@
/// \ref concept::ReadMap "ReadMap", so it is easy to change it to any
/// kind of length.
+ ///
+ /// The algorithm solves the shortest path problem for each pairs
+ /// of node when the edges can have negative length but the graph should
+ /// not contain circle with negative sum of length. If we can assume
+ /// that all edge is nonnegative in the graph then the dijkstra algorithm
+ /// should be used from each node rather and if the graph is sparse and
+ /// there are negative circles then the johson algorithm.
+ ///
+ /// The complexity of this algorithm is O(n^3 + e).
///
/// The type of the length is determined by the
Index: lemon/johnson.h
===================================================================
 lemon/johnson.h (revision 1710)
+++ lemon/johnson.h (revision 1723)
@@ 30,4 +30,5 @@
#include
#include
+#include
#include
@@ 107,12 +108,12 @@
typedef JohnsonDefaultOperationTraits OperationTraits;
 /// \brief The type of the map that stores the last edges of the
+ /// \brief The type of the matrix map that stores the last edges of the
/// shortest paths.
///
 /// The type of the map that stores the last
 /// edges of the shortest paths.
+ /// The type of the map that stores the last edges of the shortest paths.
/// It must be a matrix map with \c Graph::Edge value type.
///
 typedef NodeMatrixMap PredMap;
+ typedef DynamicMatrixMap PredMap;
/// \brief Instantiates a PredMap.
@@ 125,11 +126,11 @@
}
 /// \brief The type of the map that stores the dists of the nodes.
 ///
 /// The type of the map that stores the dists of the nodes.
 /// It must meet the \ref concept::WriteMap "WriteMap" concept.
 ///
 typedef NodeMatrixMap DistMap;

+ /// \brief The type of the matrix map that stores the dists of the nodes.
+ ///
+ /// The type of the matrix map that stores the dists of the nodes.
+ /// It must meet the \ref concept::WriteMatrixMap "WriteMatrixMap" concept.
+ ///
+ typedef DynamicMatrixMap DistMap;
+
/// \brief Instantiates a DistMap.
///
@@ 150,4 +151,13 @@
/// \ref concept::ReadMap "ReadMap", so it is easy to change it to any
/// kind of length.
+ ///
+ /// The algorithm solves the shortest path problem for each pairs
+ /// of node when the edges can have negative length but the graph should
+ /// not contain circle with negative sum of length. If we can assume
+ /// that all edge is nonnegative in the graph then the dijkstra algorithm
+ /// should be used from each node.
+ ///
+ /// 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).
///
/// The type of the length is determined by the