COIN-OR::LEMON - Graph Library

Changeset 1723:fb4f801dd692 in lemon-0.x for lemon/floyd_warshall.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/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
Note: See TracChangeset for help on using the changeset viewer.