lemon/dijkstra.h
changeset 279 6307bbbf285b
parent 258 0310c8984732
child 281 e9b4fbe163f5
child 286 da414906fe21
equal deleted inserted replaced
11:909a8392b2ee 12:cb7f4fe8515b
    28 #include <lemon/bin_heap.h>
    28 #include <lemon/bin_heap.h>
    29 #include <lemon/bits/path_dump.h>
    29 #include <lemon/bits/path_dump.h>
    30 #include <lemon/core.h>
    30 #include <lemon/core.h>
    31 #include <lemon/error.h>
    31 #include <lemon/error.h>
    32 #include <lemon/maps.h>
    32 #include <lemon/maps.h>
       
    33 #include <lemon/path.h>
    33 
    34 
    34 namespace lemon {
    35 namespace lemon {
    35 
    36 
    36   /// \brief Default operation traits for the Dijkstra algorithm class.
    37   /// \brief Default operation traits for the Dijkstra algorithm class.
    37   ///
    38   ///
   197   ///so it is easy to change it to any kind of length.
   198   ///so it is easy to change it to any kind of length.
   198   ///The type of the length is determined by the
   199   ///The type of the length is determined by the
   199   ///\ref concepts::ReadMap::Value "Value" of the length map.
   200   ///\ref concepts::ReadMap::Value "Value" of the length map.
   200   ///It is also possible to change the underlying priority heap.
   201   ///It is also possible to change the underlying priority heap.
   201   ///
   202   ///
   202   ///There is also a \ref dijkstra() "function type interface" for the
   203   ///There is also a \ref dijkstra() "function-type interface" for the
   203   ///%Dijkstra algorithm, which is convenient in the simplier cases and
   204   ///%Dijkstra algorithm, which is convenient in the simplier cases and
   204   ///it can be used easier.
   205   ///it can be used easier.
   205   ///
   206   ///
   206   ///\tparam GR The type of the digraph the algorithm runs on.
   207   ///\tparam GR The type of the digraph the algorithm runs on.
   207   ///The default value is \ref ListDigraph.
   208   ///The default value is \ref ListDigraph.
   985     ///arcs of the shortest paths.
   986     ///arcs of the shortest paths.
   986     ///
   987     ///
   987     ///The type of the map that stores the predecessor
   988     ///The type of the map that stores the predecessor
   988     ///arcs of the shortest paths.
   989     ///arcs of the shortest paths.
   989     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
   990     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
   990     typedef NullMap <typename Digraph::Node,typename Digraph::Arc> PredMap;
   991     typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
   991     ///Instantiates a \ref PredMap.
   992     ///Instantiates a \ref PredMap.
   992 
   993 
   993     ///This function instantiates a \ref PredMap.
   994     ///This function instantiates a \ref PredMap.
   994     ///\param g is the digraph, to which we would like to define the
   995     ///\param g is the digraph, to which we would like to define the
   995     ///\ref PredMap.
   996     ///\ref PredMap.
   996     ///\todo The digraph alone may be insufficient to initialize
   997     ///\todo The digraph alone may be insufficient to initialize
   997 #ifdef DOXYGEN
       
   998     static PredMap *createPredMap(const Digraph &g)
   998     static PredMap *createPredMap(const Digraph &g)
   999 #else
   999     {
  1000     static PredMap *createPredMap(const Digraph &)
  1000       return new PredMap(g);
  1001 #endif
       
  1002     {
       
  1003       return new PredMap();
       
  1004     }
  1001     }
  1005 
  1002 
  1006     ///The type of the map that indicates which nodes are processed.
  1003     ///The type of the map that indicates which nodes are processed.
  1007 
  1004 
  1008     ///The type of the map that indicates which nodes are processed.
  1005     ///The type of the map that indicates which nodes are processed.
  1028 
  1025 
  1029     ///The type of the map that stores the distances of the nodes.
  1026     ///The type of the map that stores the distances of the nodes.
  1030 
  1027 
  1031     ///The type of the map that stores the distances of the nodes.
  1028     ///The type of the map that stores the distances of the nodes.
  1032     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
  1029     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
  1033     typedef NullMap<typename Digraph::Node,Value> DistMap;
  1030     typedef typename Digraph::template NodeMap<typename LM::Value> DistMap;
  1034     ///Instantiates a \ref DistMap.
  1031     ///Instantiates a \ref DistMap.
  1035 
  1032 
  1036     ///This function instantiates a \ref DistMap.
  1033     ///This function instantiates a \ref DistMap.
  1037     ///\param g is the digraph, to which we would like to define
  1034     ///\param g is the digraph, to which we would like to define
  1038     ///the \ref DistMap
  1035     ///the \ref DistMap
  1039 #ifdef DOXYGEN
       
  1040     static DistMap *createDistMap(const Digraph &g)
  1036     static DistMap *createDistMap(const Digraph &g)
  1041 #else
  1037     {
  1042     static DistMap *createDistMap(const Digraph &)
  1038       return new DistMap(g);
  1043 #endif
  1039     }
  1044     {
  1040 
  1045       return new DistMap();
  1041     ///The type of the shortest paths.
  1046     }
  1042 
       
  1043     ///The type of the shortest paths.
       
  1044     ///It must meet the \ref concepts::Path "Path" concept.
       
  1045     typedef lemon::Path<Digraph> Path;
  1047   };
  1046   };
  1048 
  1047 
  1049   /// Default traits class used by \ref DijkstraWizard
  1048   /// Default traits class used by \ref DijkstraWizard
  1050 
  1049 
  1051   /// To make it easier to use Dijkstra algorithm
  1050   /// To make it easier to use Dijkstra algorithm
  1063     //The type of the nodes in the digraph.
  1062     //The type of the nodes in the digraph.
  1064     typedef typename Base::Digraph::Node Node;
  1063     typedef typename Base::Digraph::Node Node;
  1065 
  1064 
  1066     //Pointer to the digraph the algorithm runs on.
  1065     //Pointer to the digraph the algorithm runs on.
  1067     void *_g;
  1066     void *_g;
  1068     //Pointer to the length map
  1067     //Pointer to the length map.
  1069     void *_length;
  1068     void *_length;
  1070     //Pointer to the map of processed nodes.
  1069     //Pointer to the map of processed nodes.
  1071     void *_processed;
  1070     void *_processed;
  1072     //Pointer to the map of predecessors arcs.
  1071     //Pointer to the map of predecessors arcs.
  1073     void *_pred;
  1072     void *_pred;
  1074     //Pointer to the map of distances.
  1073     //Pointer to the map of distances.
  1075     void *_dist;
  1074     void *_dist;
  1076     //Pointer to the source node.
  1075     //Pointer to the shortest path to the target node.
  1077     Node _source;
  1076     void *_path;
       
  1077     //Pointer to the distance of the target node.
       
  1078     void *_di;
  1078 
  1079 
  1079   public:
  1080   public:
  1080     /// Constructor.
  1081     /// Constructor.
  1081 
  1082 
  1082     /// This constructor does not require parameters, therefore it initiates
  1083     /// This constructor does not require parameters, therefore it initiates
  1083     /// all of the attributes to default values (0, INVALID).
  1084     /// all of the attributes to \c 0.
  1084     DijkstraWizardBase() : _g(0), _length(0), _processed(0), _pred(0),
  1085     DijkstraWizardBase() : _g(0), _length(0), _processed(0), _pred(0),
  1085                            _dist(0), _source(INVALID) {}
  1086                            _dist(0), _path(0), _di(0) {}
  1086 
  1087 
  1087     /// Constructor.
  1088     /// Constructor.
  1088 
  1089 
  1089     /// This constructor requires some parameters,
  1090     /// This constructor requires two parameters,
  1090     /// listed in the parameters list.
  1091     /// others are initiated to \c 0.
  1091     /// Others are initiated to 0.
       
  1092     /// \param g The digraph the algorithm runs on.
  1092     /// \param g The digraph the algorithm runs on.
  1093     /// \param l The length map.
  1093     /// \param l The length map.
  1094     /// \param s The source node.
  1094     DijkstraWizardBase(const GR &g,const LM &l) :
  1095     DijkstraWizardBase(const GR &g,const LM &l, Node s=INVALID) :
       
  1096       _g(reinterpret_cast<void*>(const_cast<GR*>(&g))),
  1095       _g(reinterpret_cast<void*>(const_cast<GR*>(&g))),
  1097       _length(reinterpret_cast<void*>(const_cast<LM*>(&l))),
  1096       _length(reinterpret_cast<void*>(const_cast<LM*>(&l))),
  1098       _processed(0), _pred(0), _dist(0), _source(s) {}
  1097       _processed(0), _pred(0), _dist(0), _path(0), _di(0) {}
  1099 
  1098 
  1100   };
  1099   };
  1101 
  1100 
  1102   /// Auxiliary class for the function type interface of Dijkstra algorithm.
  1101   /// Auxiliary class for the function-type interface of Dijkstra algorithm.
  1103 
  1102 
  1104   /// This auxiliary class is created to implement the function type
  1103   /// This auxiliary class is created to implement the
  1105   /// interface of \ref Dijkstra algorithm. It uses the functions and features
  1104   /// \ref dijkstra() "function-type interface" of \ref Dijkstra algorithm.
  1106   /// of the plain \ref Dijkstra, but it is much simpler to use it.
  1105   /// It does not have own \ref run() method, it uses the functions
  1107   /// It should only be used through the \ref dijkstra() function, which makes
  1106   /// and features of the plain \ref Dijkstra.
  1108   /// it easier to use the algorithm.
       
  1109   ///
  1107   ///
  1110   /// Simplicity means that the way to change the types defined
  1108   /// This class should only be used through the \ref dijkstra() function,
  1111   /// in the traits class is based on functions that returns the new class
  1109   /// which makes it easier to use the algorithm.
  1112   /// and not on templatable built-in classes.
       
  1113   /// When using the plain \ref Dijkstra
       
  1114   /// the new class with the modified type comes from
       
  1115   /// the original class by using the ::
       
  1116   /// operator. In the case of \ref DijkstraWizard only
       
  1117   /// a function have to be called, and it will
       
  1118   /// return the needed class.
       
  1119   ///
       
  1120   /// It does not have own \ref run() method. When its \ref run() method
       
  1121   /// is called, it initiates a plain \ref Dijkstra object, and calls the
       
  1122   /// \ref Dijkstra::run() method of it.
       
  1123   template<class TR>
  1110   template<class TR>
  1124   class DijkstraWizard : public TR
  1111   class DijkstraWizard : public TR
  1125   {
  1112   {
  1126     typedef TR Base;
  1113     typedef TR Base;
  1127 
  1114 
  1142     typedef typename TR::PredMap PredMap;
  1129     typedef typename TR::PredMap PredMap;
  1143     ///The type of the map that stores the distances of the nodes.
  1130     ///The type of the map that stores the distances of the nodes.
  1144     typedef typename TR::DistMap DistMap;
  1131     typedef typename TR::DistMap DistMap;
  1145     ///The type of the map that indicates which nodes are processed.
  1132     ///The type of the map that indicates which nodes are processed.
  1146     typedef typename TR::ProcessedMap ProcessedMap;
  1133     typedef typename TR::ProcessedMap ProcessedMap;
       
  1134     ///The type of the shortest paths
       
  1135     typedef typename TR::Path Path;
  1147     ///The heap type used by the dijkstra algorithm.
  1136     ///The heap type used by the dijkstra algorithm.
  1148     typedef typename TR::Heap Heap;
  1137     typedef typename TR::Heap Heap;
  1149 
  1138 
  1150   public:
  1139   public:
  1151 
  1140 
  1154 
  1143 
  1155     /// Constructor that requires parameters.
  1144     /// Constructor that requires parameters.
  1156 
  1145 
  1157     /// Constructor that requires parameters.
  1146     /// Constructor that requires parameters.
  1158     /// These parameters will be the default values for the traits class.
  1147     /// These parameters will be the default values for the traits class.
  1159     DijkstraWizard(const Digraph &g,const LengthMap &l, Node s=INVALID) :
  1148     /// \param g The digraph the algorithm runs on.
  1160       TR(g,l,s) {}
  1149     /// \param l The length map.
       
  1150     DijkstraWizard(const Digraph &g, const LengthMap &l) :
       
  1151       TR(g,l) {}
  1161 
  1152 
  1162     ///Copy constructor
  1153     ///Copy constructor
  1163     DijkstraWizard(const TR &b) : TR(b) {}
  1154     DijkstraWizard(const TR &b) : TR(b) {}
  1164 
  1155 
  1165     ~DijkstraWizard() {}
  1156     ~DijkstraWizard() {}
  1166 
  1157 
  1167     ///Runs Dijkstra algorithm from a source node.
  1158     ///Runs Dijkstra algorithm from the given source node.
  1168 
  1159 
  1169     ///Runs Dijkstra algorithm from a source node.
  1160     ///This method runs %Dijkstra algorithm from the given source node
  1170     ///The node can be given with the \ref source() function.
  1161     ///in order to compute the shortest path to each node.
  1171     void run()
  1162     void run(Node s)
  1172     {
  1163     {
  1173       if(Base::_source==INVALID) throw UninitializedParameter();
  1164       if (s==INVALID) throw UninitializedParameter();
  1174       Dijkstra<Digraph,LengthMap,TR>
  1165       Dijkstra<Digraph,LengthMap,TR>
  1175         dij(*reinterpret_cast<const Digraph*>(Base::_g),
  1166         dijk(*reinterpret_cast<const Digraph*>(Base::_g),
  1176             *reinterpret_cast<const LengthMap*>(Base::_length));
  1167              *reinterpret_cast<const LengthMap*>(Base::_length));
  1177       if(Base::_processed)
  1168       if (Base::_pred)
  1178         dij.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed));
  1169         dijk.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
  1179       if(Base::_pred)
  1170       if (Base::_dist)
  1180         dij.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
  1171         dijk.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
  1181       if(Base::_dist)
  1172       if (Base::_processed)
  1182         dij.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
  1173         dijk.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed));
  1183       dij.run(Base::_source);
  1174       dijk.run(s);
  1184     }
  1175     }
  1185 
  1176 
  1186     ///Runs Dijkstra algorithm from the given node.
  1177     ///Finds the shortest path between \c s and \c t.
  1187 
  1178 
  1188     ///Runs Dijkstra algorithm from the given node.
  1179     ///This method runs the %Dijkstra algorithm from node \c s
  1189     ///\param s is the given source.
  1180     ///in order to compute the shortest path to node \c t
  1190     void run(Node s)
  1181     ///(it stops searching when \c t is processed).
  1191     {
  1182     ///
  1192       Base::_source=s;
  1183     ///\return \c true if \c t is reachable form \c s.
  1193       run();
  1184     bool run(Node s, Node t)
  1194     }
  1185     {
  1195 
  1186       if (s==INVALID || t==INVALID) throw UninitializedParameter();
  1196     /// Sets the source node, from which the Dijkstra algorithm runs.
  1187       Dijkstra<Digraph,LengthMap,TR>
  1197 
  1188         dijk(*reinterpret_cast<const Digraph*>(Base::_g),
  1198     /// Sets the source node, from which the Dijkstra algorithm runs.
  1189              *reinterpret_cast<const LengthMap*>(Base::_length));
  1199     /// \param s is the source node.
  1190       if (Base::_pred)
  1200     DijkstraWizard<TR> &source(Node s)
  1191         dijk.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
  1201     {
  1192       if (Base::_dist)
  1202       Base::_source=s;
  1193         dijk.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
  1203       return *this;
  1194       if (Base::_processed)
       
  1195         dijk.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed));
       
  1196       dijk.run(s,t);
       
  1197       if (Base::_path)
       
  1198         *reinterpret_cast<Path*>(Base::_path) = dijk.path(t);
       
  1199       if (Base::_di)
       
  1200         *reinterpret_cast<Value*>(Base::_di) = dijk.dist(t);
       
  1201       return dijk.reached(t);
  1204     }
  1202     }
  1205 
  1203 
  1206     template<class T>
  1204     template<class T>
  1207     struct SetPredMapBase : public Base {
  1205     struct SetPredMapBase : public Base {
  1208       typedef T PredMap;
  1206       typedef T PredMap;
  1209       static PredMap *createPredMap(const Digraph &) { return 0; };
  1207       static PredMap *createPredMap(const Digraph &) { return 0; };
  1210       SetPredMapBase(const TR &b) : TR(b) {}
  1208       SetPredMapBase(const TR &b) : TR(b) {}
  1211     };
  1209     };
  1212     ///\brief \ref named-templ-param "Named parameter"
  1210     ///\brief \ref named-func-param "Named parameter"
  1213     ///for setting \ref PredMap object.
  1211     ///for setting \ref PredMap object.
  1214     ///
  1212     ///
  1215     ///\ref named-templ-param "Named parameter"
  1213     ///\ref named-func-param "Named parameter"
  1216     ///for setting \ref PredMap object.
  1214     ///for setting \ref PredMap object.
  1217     template<class T>
  1215     template<class T>
  1218     DijkstraWizard<SetPredMapBase<T> > predMap(const T &t)
  1216     DijkstraWizard<SetPredMapBase<T> > predMap(const T &t)
  1219     {
  1217     {
  1220       Base::_pred=reinterpret_cast<void*>(const_cast<T*>(&t));
  1218       Base::_pred=reinterpret_cast<void*>(const_cast<T*>(&t));
  1221       return DijkstraWizard<SetPredMapBase<T> >(*this);
  1219       return DijkstraWizard<SetPredMapBase<T> >(*this);
       
  1220     }
       
  1221 
       
  1222     template<class T>
       
  1223     struct SetDistMapBase : public Base {
       
  1224       typedef T DistMap;
       
  1225       static DistMap *createDistMap(const Digraph &) { return 0; };
       
  1226       SetDistMapBase(const TR &b) : TR(b) {}
       
  1227     };
       
  1228     ///\brief \ref named-func-param "Named parameter"
       
  1229     ///for setting \ref DistMap object.
       
  1230     ///
       
  1231     ///\ref named-func-param "Named parameter"
       
  1232     ///for setting \ref DistMap object.
       
  1233     template<class T>
       
  1234     DijkstraWizard<SetDistMapBase<T> > distMap(const T &t)
       
  1235     {
       
  1236       Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t));
       
  1237       return DijkstraWizard<SetDistMapBase<T> >(*this);
  1222     }
  1238     }
  1223 
  1239 
  1224     template<class T>
  1240     template<class T>
  1225     struct SetProcessedMapBase : public Base {
  1241     struct SetProcessedMapBase : public Base {
  1226       typedef T ProcessedMap;
  1242       typedef T ProcessedMap;
  1227       static ProcessedMap *createProcessedMap(const Digraph &) { return 0; };
  1243       static ProcessedMap *createProcessedMap(const Digraph &) { return 0; };
  1228       SetProcessedMapBase(const TR &b) : TR(b) {}
  1244       SetProcessedMapBase(const TR &b) : TR(b) {}
  1229     };
  1245     };
  1230     ///\brief \ref named-templ-param "Named parameter"
  1246     ///\brief \ref named-func-param "Named parameter"
  1231     ///for setting \ref ProcessedMap object.
  1247     ///for setting \ref ProcessedMap object.
  1232     ///
  1248     ///
  1233     /// \ref named-templ-param "Named parameter"
  1249     /// \ref named-func-param "Named parameter"
  1234     ///for setting \ref ProcessedMap object.
  1250     ///for setting \ref ProcessedMap object.
  1235     template<class T>
  1251     template<class T>
  1236     DijkstraWizard<SetProcessedMapBase<T> > processedMap(const T &t)
  1252     DijkstraWizard<SetProcessedMapBase<T> > processedMap(const T &t)
  1237     {
  1253     {
  1238       Base::_processed=reinterpret_cast<void*>(const_cast<T*>(&t));
  1254       Base::_processed=reinterpret_cast<void*>(const_cast<T*>(&t));
  1239       return DijkstraWizard<SetProcessedMapBase<T> >(*this);
  1255       return DijkstraWizard<SetProcessedMapBase<T> >(*this);
  1240     }
  1256     }
  1241 
  1257 
  1242     template<class T>
  1258     template<class T>
  1243     struct SetDistMapBase : public Base {
  1259     struct SetPathBase : public Base {
  1244       typedef T DistMap;
  1260       typedef T Path;
  1245       static DistMap *createDistMap(const Digraph &) { return 0; };
  1261       SetPathBase(const TR &b) : TR(b) {}
  1246       SetDistMapBase(const TR &b) : TR(b) {}
  1262     };
  1247     };
  1263     ///\brief \ref named-func-param "Named parameter"
  1248     ///\brief \ref named-templ-param "Named parameter"
  1264     ///for getting the shortest path to the target node.
  1249     ///for setting \ref DistMap object.
  1265     ///
  1250     ///
  1266     ///\ref named-func-param "Named parameter"
  1251     ///\ref named-templ-param "Named parameter"
  1267     ///for getting the shortest path to the target node.
  1252     ///for setting \ref DistMap object.
       
  1253     template<class T>
  1268     template<class T>
  1254     DijkstraWizard<SetDistMapBase<T> > distMap(const T &t)
  1269     DijkstraWizard<SetPathBase<T> > path(const T &t)
  1255     {
  1270     {
  1256       Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t));
  1271       Base::_path=reinterpret_cast<void*>(const_cast<T*>(&t));
  1257       return DijkstraWizard<SetDistMapBase<T> >(*this);
  1272       return DijkstraWizard<SetPathBase<T> >(*this);
       
  1273     }
       
  1274 
       
  1275     ///\brief \ref named-func-param "Named parameter"
       
  1276     ///for getting the distance of the target node.
       
  1277     ///
       
  1278     ///\ref named-func-param "Named parameter"
       
  1279     ///for getting the distance of the target node.
       
  1280     DijkstraWizard dist(const Value &d)
       
  1281     {
       
  1282       Base::_di=reinterpret_cast<void*>(const_cast<Value*>(&d));
       
  1283       return *this;
  1258     }
  1284     }
  1259 
  1285 
  1260   };
  1286   };
  1261 
  1287 
  1262   ///Function type interface for Dijkstra algorithm.
  1288   ///Function-type interface for Dijkstra algorithm.
  1263 
  1289 
  1264   /// \ingroup shortest_path
  1290   /// \ingroup shortest_path
  1265   ///Function type interface for Dijkstra algorithm.
  1291   ///Function-type interface for Dijkstra algorithm.
  1266   ///
  1292   ///
  1267   ///This function also has several
  1293   ///This function also has several \ref named-func-param "named parameters",
  1268   ///\ref named-templ-func-param "named parameters",
       
  1269   ///they are declared as the members of class \ref DijkstraWizard.
  1294   ///they are declared as the members of class \ref DijkstraWizard.
  1270   ///The following
  1295   ///The following examples show how to use these parameters.
  1271   ///example shows how to use these parameters.
       
  1272   ///\code
  1296   ///\code
  1273   ///  dijkstra(g,length,source).predMap(preds).run();
  1297   ///  // Compute shortest path from node s to each node
       
  1298   ///  dijkstra(g,length).predMap(preds).distMap(dists).run(s);
       
  1299   ///
       
  1300   ///  // Compute shortest path from s to t
       
  1301   ///  bool reached = dijkstra(g,length).path(p).dist(d).run(s,t);
  1274   ///\endcode
  1302   ///\endcode
  1275   ///\warning Don't forget to put the \ref DijkstraWizard::run() "run()"
  1303   ///\warning Don't forget to put the \ref DijkstraWizard::run() "run()"
  1276   ///to the end of the parameter list.
  1304   ///to the end of the parameter list.
  1277   ///\sa DijkstraWizard
  1305   ///\sa DijkstraWizard
  1278   ///\sa Dijkstra
  1306   ///\sa Dijkstra
  1279   template<class GR, class LM>
  1307   template<class GR, class LM>
  1280   DijkstraWizard<DijkstraWizardBase<GR,LM> >
  1308   DijkstraWizard<DijkstraWizardBase<GR,LM> >
  1281   dijkstra(const GR &g,const LM &l,typename GR::Node s=INVALID)
  1309   dijkstra(const GR &digraph, const LM &length)
  1282   {
  1310   {
  1283     return DijkstraWizard<DijkstraWizardBase<GR,LM> >(g,l,s);
  1311     return DijkstraWizard<DijkstraWizardBase<GR,LM> >(digraph,length);
  1284   }
  1312   }
  1285 
  1313 
  1286 } //END OF NAMESPACE LEMON
  1314 } //END OF NAMESPACE LEMON
  1287 
  1315 
  1288 #endif
  1316 #endif