# HG changeset patch # User deba # Date 1129287231 0 # Node ID fb4f801dd69250daff8dc0e29b176b8d48b78421 # Parent 2acb5f9bfa72050cd5697bc75e689bc66aae72aa Really short description of these shortest path algorithms diff -r 2acb5f9bfa72 -r fb4f801dd692 lemon/belmann_ford.h --- a/lemon/belmann_ford.h Fri Oct 14 10:53:35 2005 +0000 +++ b/lemon/belmann_ford.h Fri Oct 14 10:53:51 2005 +0000 @@ -144,11 +144,19 @@ /// \brief BelmannFord algorithm class. /// /// \ingroup flowalgs - /// This class provides an efficient implementation of \c BelmannFord + /// This class provides an efficient implementation of \c Belmann-Ford /// 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 Belmann-Ford 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 non-negative 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 /// \ref concept::ReadMap::Value "Value" of the length map. /// @@ -402,9 +410,9 @@ /// - The shortest path tree. /// - 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); Node target = graph->target(it); @@ -416,8 +424,40 @@ ready = false; } } + 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; + } /// \brief Runs %BelmannFord algorithm from node \c s. /// diff -r 2acb5f9bfa72 -r fb4f801dd692 lemon/floyd_warshall.h --- a/lemon/floyd_warshall.h Fri Oct 14 10:53:35 2005 +0000 +++ b/lemon/floyd_warshall.h Fri Oct 14 10:53:51 2005 +0000 @@ -27,6 +27,7 @@ #include #include #include +#include #include #include @@ -105,14 +106,14 @@ /// \see FloydWarshallDefaultOperationTraits 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. /// @@ -126,9 +127,9 @@ /// \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. + /// It must meet the \ref concept::WriteMatrixMap "WriteMatrixMap" concept. /// - typedef NodeMatrixMap DistMap; + typedef DynamicMatrixMap DistMap; /// \brief Instantiates a DistMap. /// @@ -149,6 +150,15 @@ /// \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 non-negative 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 /// \ref concept::ReadMap::Value "Value" of the length map. /// diff -r 2acb5f9bfa72 -r fb4f801dd692 lemon/johnson.h --- a/lemon/johnson.h Fri Oct 14 10:53:35 2005 +0000 +++ b/lemon/johnson.h Fri Oct 14 10:53:51 2005 +0000 @@ -29,6 +29,7 @@ #include #include #include +#include #include @@ -106,14 +107,14 @@ /// \see JohnsonDefaultOperationTraits 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. /// @@ -124,13 +125,13 @@ return new PredMap(graph); } - /// \brief The type of the map that stores the dists of the nodes. + /// \brief The type of the matrix 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. + /// The type of the matrix map that stores the dists of the nodes. + /// It must meet the \ref concept::WriteMatrixMap "WriteMatrixMap" concept. /// - typedef NodeMatrixMap DistMap; - + typedef DynamicMatrixMap DistMap; + /// \brief Instantiates a DistMap. /// /// This function instantiates a \ref DistMap. @@ -150,6 +151,15 @@ /// \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 non-negative 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 /// \ref concept::ReadMap::Value "Value" of the length map. ///