# Changeset 1723:fb4f801dd692 in lemon-0.x for lemon

Ignore:
Timestamp:
10/14/05 12:53:51 (14 years ago)
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
 r1710 #include #include #include #include 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. } /// \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. /// /// \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