COIN-OR::LEMON - Graph Library

Changeset 1723:fb4f801dd692 in lemon-0.x


Ignore:
Timestamp:
10/14/05 12:53:51 (14 years ago)
Author:
Balazs Dezso
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2250
Message:

Really short description of these shortest path algorithms

Location:
lemon
Files:
3 edited

Legend:

Unmodified
Added
Removed
  • lemon/belmann_ford.h

    r1710 r1723  
    145145  ///
    146146  /// \ingroup flowalgs
    147   /// This class provides an efficient implementation of \c BelmannFord
     147  /// This class provides an efficient implementation of \c Belmann-Ford
    148148  /// algorithm. The edge lengths are passed to the algorithm using a
    149149  /// \ref concept::ReadMap "ReadMap", so it is easy to change it to any
    150150  /// kind of length.
     151  ///
     152  /// The Belmann-Ford algorithm solves the shortest path from one node
     153  /// problem when the edges can have negative length but the graph should
     154  /// not contain circle with negative sum of length. If we can assume
     155  /// that all edge is non-negative in the graph then the dijkstra algorithm
     156  /// should be used rather.
     157  ///
     158  /// The complexity of the algorithm is O(n * e).
    151159  ///
    152160  /// The type of the length is determined by the
     
    403411    /// - The distance of each node from the root(s).
    404412    void start() {
    405       bool ready = false;
    406       while (!ready) {
    407         ready = true;
     413      int num = countNodes(*graph) - 1;
     414      for (int i = 0; i < num; ++i) {
     415        bool ready = true;
    408416        for (EdgeIt it(*graph); it != INVALID; ++it) {
    409417          Node source = graph->source(it);
     
    417425          }
    418426        }
    419       }
     427        if (ready) return;
     428      }
     429    }
     430
     431    /// \brief Executes the algorithm and check the negative circles.
     432    ///
     433    /// \pre init() must be called and at least one node should be added
     434    /// with addSource() before using this function. If there is
     435    /// a negative circle in the graph it gives back false.
     436    ///
     437    /// This method runs the %BelmannFord algorithm from the root node(s)
     438    /// in order to compute the shortest path to each node. The algorithm
     439    /// computes
     440    /// - The shortest path tree.
     441    /// - The distance of each node from the root(s).
     442    bool checkedStart() {
     443      int num = countNodes(*graph);
     444      for (int i = 0; i < num; ++i) {
     445        bool ready = true;
     446        for (EdgeIt it(*graph); it != INVALID; ++it) {
     447          Node source = graph->source(it);
     448          Node target = graph->target(it);
     449          Value relaxed =
     450            OperationTraits::plus((*_dist)[source], (*length)[it]);
     451          if (OperationTraits::less(relaxed, (*_dist)[target])) {
     452            _pred->set(target, it);
     453            _dist->set(target, relaxed);
     454            ready = false;
     455          }
     456        }
     457        if (ready) return true;
     458      }
     459      return false;
    420460    }
    421461   
  • lemon/floyd_warshall.h

    r1710 r1723  
    2828#include <lemon/invalid.h>
    2929#include <lemon/error.h>
     30#include <lemon/matrix_maps.h>
    3031#include <lemon/maps.h>
    3132
     
    106107    typedef FloydWarshallDefaultOperationTraits<Value> OperationTraits;
    107108 
    108     /// \brief The type of the map that stores the last edges of the
     109    /// \brief The type of the matrix map that stores the last edges of the
    109110    /// shortest paths.
    110111    ///
    111     /// The type of the map that stores the last
    112     /// edges of the shortest paths.
     112    /// The type of the map that stores the last edges of the shortest paths.
    113113    /// It must be a matrix map with \c Graph::Edge value type.
    114114    ///
    115     typedef NodeMatrixMap<Graph, typename Graph::Edge> PredMap;
     115    typedef DynamicMatrixMap<Graph, typename Graph::Node,
     116                             typename Graph::Edge> PredMap;
    116117
    117118    /// \brief Instantiates a PredMap.
     
    127128    ///
    128129    /// The type of the map that stores the dists of the nodes.
    129     /// It must meet the \ref concept::WriteMap "WriteMap" concept.
    130     ///
    131     typedef NodeMatrixMap<Graph, Value> DistMap;
     130    /// It must meet the \ref concept::WriteMatrixMap "WriteMatrixMap" concept.
     131    ///
     132    typedef DynamicMatrixMap<Graph, typename Graph::Node, Value> DistMap;
    132133
    133134    /// \brief Instantiates a DistMap.
     
    149150  /// \ref concept::ReadMap "ReadMap", so it is easy to change it to any
    150151  /// kind of length.
     152  ///
     153  /// The algorithm solves the shortest path problem for each pairs
     154  /// of node when the edges can have negative length but the graph should
     155  /// not contain circle with negative sum of length. If we can assume
     156  /// that all edge is non-negative in the graph then the dijkstra algorithm
     157  /// should be used from each node rather and if the graph is sparse and
     158  /// there are negative circles then the johson algorithm.
     159  ///
     160  /// The complexity of this algorithm is O(n^3 + e).
    151161  ///
    152162  /// The type of the length is determined by the
  • lemon/johnson.h

    r1710 r1723  
    3030#include <lemon/error.h>
    3131#include <lemon/maps.h>
     32#include <lemon/matrix_maps.h>
    3233
    3334#include <limits>
     
    107108    typedef JohnsonDefaultOperationTraits<Value> OperationTraits;
    108109 
    109     /// \brief The type of the map that stores the last edges of the
     110    /// \brief The type of the matrix map that stores the last edges of the
    110111    /// shortest paths.
    111112    ///
    112     /// The type of the map that stores the last
    113     /// edges of the shortest paths.
     113    /// The type of the map that stores the last edges of the shortest paths.
    114114    /// It must be a matrix map with \c Graph::Edge value type.
    115115    ///
    116     typedef NodeMatrixMap<Graph, typename Graph::Edge> PredMap;
     116    typedef DynamicMatrixMap<Graph, typename Graph::Node,
     117                             typename Graph::Edge> PredMap;
    117118
    118119    /// \brief Instantiates a PredMap.
     
    125126    }
    126127
    127     /// \brief The type of the map that stores the dists of the nodes.
    128     ///
    129     /// The type of the map that stores the dists of the nodes.
    130     /// It must meet the \ref concept::WriteMap "WriteMap" concept.
    131     ///
    132     typedef NodeMatrixMap<Graph, Value> DistMap;
    133 
     128    /// \brief The type of the matrix map that stores the dists of the nodes.
     129    ///
     130    /// The type of the matrix map that stores the dists of the nodes.
     131    /// It must meet the \ref concept::WriteMatrixMap "WriteMatrixMap" concept.
     132    ///
     133    typedef DynamicMatrixMap<Graph, typename Graph::Node, Value> DistMap;
     134   
    134135    /// \brief Instantiates a DistMap.
    135136    ///
     
    150151  /// \ref concept::ReadMap "ReadMap", so it is easy to change it to any
    151152  /// kind of length.
     153  ///
     154  /// The algorithm solves the shortest path problem for each pairs
     155  /// of node when the edges can have negative length but the graph should
     156  /// not contain circle with negative sum of length. If we can assume
     157  /// that all edge is non-negative in the graph then the dijkstra algorithm
     158  /// should be used from each node.
     159  ///
     160  /// The complexity of this algorithm is $O(n^2 * log(n) + n * log(n) * e)$ or
     161  /// with fibonacci heap O(n^2 * log(n) + n * e).
    152162  ///
    153163  /// The type of the length is determined by the
Note: See TracChangeset for help on using the changeset viewer.