114 ///\brief The type of the map that stores the predecessor |
114 ///\brief The type of the map that stores the predecessor |
115 ///arcs of the shortest paths. |
115 ///arcs of the shortest paths. |
116 /// |
116 /// |
117 ///The type of the map that stores the predecessor |
117 ///The type of the map that stores the predecessor |
118 ///arcs of the shortest paths. |
118 ///arcs of the shortest paths. |
119 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. |
119 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. |
120 typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap; |
120 typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap; |
121 ///Instantiates a \c PredMap. |
121 ///Instantiates a \c PredMap. |
122 |
122 |
123 ///This function instantiates a \ref PredMap. |
123 ///This function instantiates a \ref PredMap. |
124 ///\param g is the digraph, to which we would like to define the |
124 ///\param g is the digraph, to which we would like to define the |
166 |
166 |
167 ///%Dijkstra algorithm class. |
167 ///%Dijkstra algorithm class. |
168 |
168 |
169 /// \ingroup shortest_path |
169 /// \ingroup shortest_path |
170 ///This class provides an efficient implementation of the %Dijkstra algorithm. |
170 ///This class provides an efficient implementation of the %Dijkstra algorithm. |
|
171 /// |
|
172 ///The %Dijkstra algorithm solves the single-source shortest path problem |
|
173 ///when all arc lengths are non-negative. If there are negative lengths, |
|
174 ///the BellmanFord algorithm should be used instead. |
171 /// |
175 /// |
172 ///The arc lengths are passed to the algorithm using a |
176 ///The arc lengths are passed to the algorithm using a |
173 ///\ref concepts::ReadMap "ReadMap", |
177 ///\ref concepts::ReadMap "ReadMap", |
174 ///so it is easy to change it to any kind of length. |
178 ///so it is easy to change it to any kind of length. |
175 ///The type of the length is determined by the |
179 ///The type of the length is determined by the |
344 ///\brief \ref named-templ-param "Named parameter" for setting |
348 ///\brief \ref named-templ-param "Named parameter" for setting |
345 ///\c ProcessedMap type. |
349 ///\c ProcessedMap type. |
346 /// |
350 /// |
347 ///\ref named-templ-param "Named parameter" for setting |
351 ///\ref named-templ-param "Named parameter" for setting |
348 ///\c ProcessedMap type. |
352 ///\c ProcessedMap type. |
349 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. |
353 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. |
350 template <class T> |
354 template <class T> |
351 struct SetProcessedMap |
355 struct SetProcessedMap |
352 : public Dijkstra< Digraph, LengthMap, SetProcessedMapTraits<T> > { |
356 : public Dijkstra< Digraph, LengthMap, SetProcessedMapTraits<T> > { |
353 typedef Dijkstra< Digraph, LengthMap, SetProcessedMapTraits<T> > Create; |
357 typedef Dijkstra< Digraph, LengthMap, SetProcessedMapTraits<T> > Create; |
354 }; |
358 }; |
441 /// \brief \ref named-templ-param "Named parameter" for setting |
445 /// \brief \ref named-templ-param "Named parameter" for setting |
442 ///\c OperationTraits type |
446 ///\c OperationTraits type |
443 /// |
447 /// |
444 ///\ref named-templ-param "Named parameter" for setting |
448 ///\ref named-templ-param "Named parameter" for setting |
445 ///\c OperationTraits type. |
449 ///\c OperationTraits type. |
|
450 /// For more information see \ref DijkstraDefaultOperationTraits. |
446 template <class T> |
451 template <class T> |
447 struct SetOperationTraits |
452 struct SetOperationTraits |
448 : public Dijkstra<Digraph, LengthMap, SetOperationTraitsTraits<T> > { |
453 : public Dijkstra<Digraph, LengthMap, SetOperationTraitsTraits<T> > { |
449 typedef Dijkstra<Digraph, LengthMap, SetOperationTraitsTraits<T> > |
454 typedef Dijkstra<Digraph, LengthMap, SetOperationTraitsTraits<T> > |
450 Create; |
455 Create; |
799 ///@} |
804 ///@} |
800 |
805 |
801 ///\name Query Functions |
806 ///\name Query Functions |
802 ///The results of the %Dijkstra algorithm can be obtained using these |
807 ///The results of the %Dijkstra algorithm can be obtained using these |
803 ///functions.\n |
808 ///functions.\n |
804 ///Either \ref run(Node) "run()" or \ref start() should be called |
809 ///Either \ref run(Node) "run()" or \ref init() should be called |
805 ///before using them. |
810 ///before using them. |
806 |
811 |
807 ///@{ |
812 ///@{ |
808 |
813 |
809 ///The shortest path to a node. |
814 ///The shortest path to the given node. |
810 |
815 |
811 ///Returns the shortest path to a node. |
816 ///Returns the shortest path to the given node from the root(s). |
812 /// |
817 /// |
813 ///\warning \c t should be reached from the root(s). |
818 ///\warning \c t should be reached from the root(s). |
814 /// |
819 /// |
815 ///\pre Either \ref run(Node) "run()" or \ref init() |
820 ///\pre Either \ref run(Node) "run()" or \ref init() |
816 ///must be called before using this function. |
821 ///must be called before using this function. |
817 Path path(Node t) const { return Path(*G, *_pred, t); } |
822 Path path(Node t) const { return Path(*G, *_pred, t); } |
818 |
823 |
819 ///The distance of a node from the root(s). |
824 ///The distance of the given node from the root(s). |
820 |
825 |
821 ///Returns the distance of a node from the root(s). |
826 ///Returns the distance of the given node from the root(s). |
822 /// |
827 /// |
823 ///\warning If node \c v is not reached from the root(s), then |
828 ///\warning If node \c v is not reached from the root(s), then |
824 ///the return value of this function is undefined. |
829 ///the return value of this function is undefined. |
825 /// |
830 /// |
826 ///\pre Either \ref run(Node) "run()" or \ref init() |
831 ///\pre Either \ref run(Node) "run()" or \ref init() |
827 ///must be called before using this function. |
832 ///must be called before using this function. |
828 Value dist(Node v) const { return (*_dist)[v]; } |
833 Value dist(Node v) const { return (*_dist)[v]; } |
829 |
834 |
830 ///Returns the 'previous arc' of the shortest path tree for a node. |
835 ///\brief Returns the 'previous arc' of the shortest path tree for |
831 |
836 ///the given node. |
|
837 /// |
832 ///This function returns the 'previous arc' of the shortest path |
838 ///This function returns the 'previous arc' of the shortest path |
833 ///tree for the node \c v, i.e. it returns the last arc of a |
839 ///tree for the node \c v, i.e. it returns the last arc of a |
834 ///shortest path from a root to \c v. It is \c INVALID if \c v |
840 ///shortest path from a root to \c v. It is \c INVALID if \c v |
835 ///is not reached from the root(s) or if \c v is a root. |
841 ///is not reached from the root(s) or if \c v is a root. |
836 /// |
842 /// |
837 ///The shortest path tree used here is equal to the shortest path |
843 ///The shortest path tree used here is equal to the shortest path |
838 ///tree used in \ref predNode(). |
844 ///tree used in \ref predNode() and \ref predMap(). |
839 /// |
845 /// |
840 ///\pre Either \ref run(Node) "run()" or \ref init() |
846 ///\pre Either \ref run(Node) "run()" or \ref init() |
841 ///must be called before using this function. |
847 ///must be called before using this function. |
842 Arc predArc(Node v) const { return (*_pred)[v]; } |
848 Arc predArc(Node v) const { return (*_pred)[v]; } |
843 |
849 |
844 ///Returns the 'previous node' of the shortest path tree for a node. |
850 ///\brief Returns the 'previous node' of the shortest path tree for |
845 |
851 ///the given node. |
|
852 /// |
846 ///This function returns the 'previous node' of the shortest path |
853 ///This function returns the 'previous node' of the shortest path |
847 ///tree for the node \c v, i.e. it returns the last but one node |
854 ///tree for the node \c v, i.e. it returns the last but one node |
848 ///from a shortest path from a root to \c v. It is \c INVALID |
855 ///of a shortest path from a root to \c v. It is \c INVALID |
849 ///if \c v is not reached from the root(s) or if \c v is a root. |
856 ///if \c v is not reached from the root(s) or if \c v is a root. |
850 /// |
857 /// |
851 ///The shortest path tree used here is equal to the shortest path |
858 ///The shortest path tree used here is equal to the shortest path |
852 ///tree used in \ref predArc(). |
859 ///tree used in \ref predArc() and \ref predMap(). |
853 /// |
860 /// |
854 ///\pre Either \ref run(Node) "run()" or \ref init() |
861 ///\pre Either \ref run(Node) "run()" or \ref init() |
855 ///must be called before using this function. |
862 ///must be called before using this function. |
856 Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID: |
863 Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID: |
857 G->source((*_pred)[v]); } |
864 G->source((*_pred)[v]); } |
868 |
875 |
869 ///\brief Returns a const reference to the node map that stores the |
876 ///\brief Returns a const reference to the node map that stores the |
870 ///predecessor arcs. |
877 ///predecessor arcs. |
871 /// |
878 /// |
872 ///Returns a const reference to the node map that stores the predecessor |
879 ///Returns a const reference to the node map that stores the predecessor |
873 ///arcs, which form the shortest path tree. |
880 ///arcs, which form the shortest path tree (forest). |
874 /// |
881 /// |
875 ///\pre Either \ref run(Node) "run()" or \ref init() |
882 ///\pre Either \ref run(Node) "run()" or \ref init() |
876 ///must be called before using this function. |
883 ///must be called before using this function. |
877 const PredMap &predMap() const { return *_pred;} |
884 const PredMap &predMap() const { return *_pred;} |
878 |
885 |
879 ///Checks if a node is reached from the root(s). |
886 ///Checks if the given node is reached from the root(s). |
880 |
887 |
881 ///Returns \c true if \c v is reached from the root(s). |
888 ///Returns \c true if \c v is reached from the root(s). |
882 /// |
889 /// |
883 ///\pre Either \ref run(Node) "run()" or \ref init() |
890 ///\pre Either \ref run(Node) "run()" or \ref init() |
884 ///must be called before using this function. |
891 ///must be called before using this function. |
893 ///\pre Either \ref run(Node) "run()" or \ref init() |
900 ///\pre Either \ref run(Node) "run()" or \ref init() |
894 ///must be called before using this function. |
901 ///must be called before using this function. |
895 bool processed(Node v) const { return (*_heap_cross_ref)[v] == |
902 bool processed(Node v) const { return (*_heap_cross_ref)[v] == |
896 Heap::POST_HEAP; } |
903 Heap::POST_HEAP; } |
897 |
904 |
898 ///The current distance of a node from the root(s). |
905 ///The current distance of the given node from the root(s). |
899 |
906 |
900 ///Returns the current distance of a node from the root(s). |
907 ///Returns the current distance of the given node from the root(s). |
901 ///It may be decreased in the following processes. |
908 ///It may be decreased in the following processes. |
902 /// |
909 /// |
903 ///\pre Either \ref run(Node) "run()" or \ref init() |
910 ///\pre Either \ref run(Node) "run()" or \ref init() |
904 ///must be called before using this function and |
911 ///must be called before using this function and |
905 ///node \c v must be reached but not necessarily processed. |
912 ///node \c v must be reached but not necessarily processed. |
922 ///The type of the digraph the algorithm runs on. |
929 ///The type of the digraph the algorithm runs on. |
923 typedef GR Digraph; |
930 typedef GR Digraph; |
924 ///The type of the map that stores the arc lengths. |
931 ///The type of the map that stores the arc lengths. |
925 |
932 |
926 ///The type of the map that stores the arc lengths. |
933 ///The type of the map that stores the arc lengths. |
927 ///It must meet the \ref concepts::ReadMap "ReadMap" concept. |
934 ///It must conform to the \ref concepts::ReadMap "ReadMap" concept. |
928 typedef LEN LengthMap; |
935 typedef LEN LengthMap; |
929 ///The type of the length of the arcs. |
936 ///The type of the arc lengths. |
930 typedef typename LEN::Value Value; |
937 typedef typename LEN::Value Value; |
931 |
938 |
932 /// Operation traits for Dijkstra algorithm. |
939 /// Operation traits for Dijkstra algorithm. |
933 |
940 |
934 /// This class defines the operations that are used in the algorithm. |
941 /// This class defines the operations that are used in the algorithm. |
971 ///\brief The type of the map that stores the predecessor |
978 ///\brief The type of the map that stores the predecessor |
972 ///arcs of the shortest paths. |
979 ///arcs of the shortest paths. |
973 /// |
980 /// |
974 ///The type of the map that stores the predecessor |
981 ///The type of the map that stores the predecessor |
975 ///arcs of the shortest paths. |
982 ///arcs of the shortest paths. |
976 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. |
983 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. |
977 typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap; |
984 typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap; |
978 ///Instantiates a PredMap. |
985 ///Instantiates a PredMap. |
979 |
986 |
980 ///This function instantiates a PredMap. |
987 ///This function instantiates a PredMap. |
981 ///\param g is the digraph, to which we would like to define the |
988 ///\param g is the digraph, to which we would like to define the |
1021 } |
1028 } |
1022 |
1029 |
1023 ///The type of the shortest paths. |
1030 ///The type of the shortest paths. |
1024 |
1031 |
1025 ///The type of the shortest paths. |
1032 ///The type of the shortest paths. |
1026 ///It must meet the \ref concepts::Path "Path" concept. |
1033 ///It must conform to the \ref concepts::Path "Path" concept. |
1027 typedef lemon::Path<Digraph> Path; |
1034 typedef lemon::Path<Digraph> Path; |
1028 }; |
1035 }; |
1029 |
1036 |
1030 /// Default traits class used by DijkstraWizard |
1037 /// Default traits class used by DijkstraWizard |
1031 |
1038 |
1032 /// To make it easier to use Dijkstra algorithm |
1039 /// Default traits class used by DijkstraWizard. |
1033 /// we have created a wizard class. |
1040 /// \tparam GR The type of the digraph. |
1034 /// This \ref DijkstraWizard class needs default traits, |
1041 /// \tparam LEN The type of the length map. |
1035 /// as well as the \ref Dijkstra class. |
|
1036 /// The \ref DijkstraWizardBase is a class to be the default traits of the |
|
1037 /// \ref DijkstraWizard class. |
|
1038 template<typename GR, typename LEN> |
1042 template<typename GR, typename LEN> |
1039 class DijkstraWizardBase : public DijkstraWizardDefaultTraits<GR,LEN> |
1043 class DijkstraWizardBase : public DijkstraWizardDefaultTraits<GR,LEN> |
1040 { |
1044 { |
1041 typedef DijkstraWizardDefaultTraits<GR,LEN> Base; |
1045 typedef DijkstraWizardDefaultTraits<GR,LEN> Base; |
1042 protected: |
1046 protected: |
1091 template<class TR> |
1095 template<class TR> |
1092 class DijkstraWizard : public TR |
1096 class DijkstraWizard : public TR |
1093 { |
1097 { |
1094 typedef TR Base; |
1098 typedef TR Base; |
1095 |
1099 |
1096 ///The type of the digraph the algorithm runs on. |
|
1097 typedef typename TR::Digraph Digraph; |
1100 typedef typename TR::Digraph Digraph; |
1098 |
1101 |
1099 typedef typename Digraph::Node Node; |
1102 typedef typename Digraph::Node Node; |
1100 typedef typename Digraph::NodeIt NodeIt; |
1103 typedef typename Digraph::NodeIt NodeIt; |
1101 typedef typename Digraph::Arc Arc; |
1104 typedef typename Digraph::Arc Arc; |
1102 typedef typename Digraph::OutArcIt OutArcIt; |
1105 typedef typename Digraph::OutArcIt OutArcIt; |
1103 |
1106 |
1104 ///The type of the map that stores the arc lengths. |
|
1105 typedef typename TR::LengthMap LengthMap; |
1107 typedef typename TR::LengthMap LengthMap; |
1106 ///The type of the length of the arcs. |
|
1107 typedef typename LengthMap::Value Value; |
1108 typedef typename LengthMap::Value Value; |
1108 ///\brief The type of the map that stores the predecessor |
|
1109 ///arcs of the shortest paths. |
|
1110 typedef typename TR::PredMap PredMap; |
1109 typedef typename TR::PredMap PredMap; |
1111 ///The type of the map that stores the distances of the nodes. |
|
1112 typedef typename TR::DistMap DistMap; |
1110 typedef typename TR::DistMap DistMap; |
1113 ///The type of the map that indicates which nodes are processed. |
|
1114 typedef typename TR::ProcessedMap ProcessedMap; |
1111 typedef typename TR::ProcessedMap ProcessedMap; |
1115 ///The type of the shortest paths |
|
1116 typedef typename TR::Path Path; |
1112 typedef typename TR::Path Path; |
1117 ///The heap type used by the dijkstra algorithm. |
|
1118 typedef typename TR::Heap Heap; |
1113 typedef typename TR::Heap Heap; |
1119 |
1114 |
1120 public: |
1115 public: |
1121 |
1116 |
1122 /// Constructor. |
1117 /// Constructor. |
1184 struct SetPredMapBase : public Base { |
1179 struct SetPredMapBase : public Base { |
1185 typedef T PredMap; |
1180 typedef T PredMap; |
1186 static PredMap *createPredMap(const Digraph &) { return 0; }; |
1181 static PredMap *createPredMap(const Digraph &) { return 0; }; |
1187 SetPredMapBase(const TR &b) : TR(b) {} |
1182 SetPredMapBase(const TR &b) : TR(b) {} |
1188 }; |
1183 }; |
1189 ///\brief \ref named-func-param "Named parameter" |
1184 |
1190 ///for setting PredMap object. |
1185 ///\brief \ref named-templ-param "Named parameter" for setting |
1191 /// |
1186 ///the predecessor map. |
1192 ///\ref named-func-param "Named parameter" |
1187 /// |
1193 ///for setting PredMap object. |
1188 ///\ref named-templ-param "Named parameter" function for setting |
|
1189 ///the map that stores the predecessor arcs of the nodes. |
1194 template<class T> |
1190 template<class T> |
1195 DijkstraWizard<SetPredMapBase<T> > predMap(const T &t) |
1191 DijkstraWizard<SetPredMapBase<T> > predMap(const T &t) |
1196 { |
1192 { |
1197 Base::_pred=reinterpret_cast<void*>(const_cast<T*>(&t)); |
1193 Base::_pred=reinterpret_cast<void*>(const_cast<T*>(&t)); |
1198 return DijkstraWizard<SetPredMapBase<T> >(*this); |
1194 return DijkstraWizard<SetPredMapBase<T> >(*this); |
1202 struct SetDistMapBase : public Base { |
1198 struct SetDistMapBase : public Base { |
1203 typedef T DistMap; |
1199 typedef T DistMap; |
1204 static DistMap *createDistMap(const Digraph &) { return 0; }; |
1200 static DistMap *createDistMap(const Digraph &) { return 0; }; |
1205 SetDistMapBase(const TR &b) : TR(b) {} |
1201 SetDistMapBase(const TR &b) : TR(b) {} |
1206 }; |
1202 }; |
1207 ///\brief \ref named-func-param "Named parameter" |
1203 |
1208 ///for setting DistMap object. |
1204 ///\brief \ref named-templ-param "Named parameter" for setting |
1209 /// |
1205 ///the distance map. |
1210 ///\ref named-func-param "Named parameter" |
1206 /// |
1211 ///for setting DistMap object. |
1207 ///\ref named-templ-param "Named parameter" function for setting |
|
1208 ///the map that stores the distances of the nodes calculated |
|
1209 ///by the algorithm. |
1212 template<class T> |
1210 template<class T> |
1213 DijkstraWizard<SetDistMapBase<T> > distMap(const T &t) |
1211 DijkstraWizard<SetDistMapBase<T> > distMap(const T &t) |
1214 { |
1212 { |
1215 Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t)); |
1213 Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t)); |
1216 return DijkstraWizard<SetDistMapBase<T> >(*this); |
1214 return DijkstraWizard<SetDistMapBase<T> >(*this); |
1220 struct SetProcessedMapBase : public Base { |
1218 struct SetProcessedMapBase : public Base { |
1221 typedef T ProcessedMap; |
1219 typedef T ProcessedMap; |
1222 static ProcessedMap *createProcessedMap(const Digraph &) { return 0; }; |
1220 static ProcessedMap *createProcessedMap(const Digraph &) { return 0; }; |
1223 SetProcessedMapBase(const TR &b) : TR(b) {} |
1221 SetProcessedMapBase(const TR &b) : TR(b) {} |
1224 }; |
1222 }; |
1225 ///\brief \ref named-func-param "Named parameter" |
1223 |
1226 ///for setting ProcessedMap object. |
1224 ///\brief \ref named-func-param "Named parameter" for setting |
1227 /// |
1225 ///the processed map. |
1228 /// \ref named-func-param "Named parameter" |
1226 /// |
1229 ///for setting ProcessedMap object. |
1227 ///\ref named-templ-param "Named parameter" function for setting |
|
1228 ///the map that indicates which nodes are processed. |
1230 template<class T> |
1229 template<class T> |
1231 DijkstraWizard<SetProcessedMapBase<T> > processedMap(const T &t) |
1230 DijkstraWizard<SetProcessedMapBase<T> > processedMap(const T &t) |
1232 { |
1231 { |
1233 Base::_processed=reinterpret_cast<void*>(const_cast<T*>(&t)); |
1232 Base::_processed=reinterpret_cast<void*>(const_cast<T*>(&t)); |
1234 return DijkstraWizard<SetProcessedMapBase<T> >(*this); |
1233 return DijkstraWizard<SetProcessedMapBase<T> >(*this); |