COIN-OR::LEMON - Graph Library

Changeset 1723:fb4f801dd692 in lemon-0.x for lemon/johnson.h


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

File:
1 edited

Legend:

Unmodified
Added
Removed
  • 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.