46 ///The graph type the algorithm runs on. |
46 ///The graph type the algorithm runs on. |
47 typedef GR Graph; |
47 typedef GR Graph; |
48 ///The type of the map that stores the edge lengths. |
48 ///The type of the map that stores the edge lengths. |
49 |
49 |
50 ///The type of the map that stores the edge lengths. |
50 ///The type of the map that stores the edge lengths. |
51 ///It must meet the \ref concept::ReadMap "ReadMap" concept. |
51 ///It must meet the \ref concepts::ReadMap "ReadMap" concept. |
52 typedef LM LengthMap; |
52 typedef LM LengthMap; |
53 //The type of the length of the edges. |
53 //The type of the length of the edges. |
54 typedef typename LM::Value Value; |
54 typedef typename LM::Value Value; |
55 /// The cross reference type used by heap. |
55 /// The cross reference type used by heap. |
56 |
56 |
84 ///\brief The type of the map that stores the last |
84 ///\brief The type of the map that stores the last |
85 ///edges of the shortest paths. |
85 ///edges of the shortest paths. |
86 /// |
86 /// |
87 ///The type of the map that stores the last |
87 ///The type of the map that stores the last |
88 ///edges of the shortest paths. |
88 ///edges of the shortest paths. |
89 ///It must meet the \ref concept::WriteMap "WriteMap" concept. |
89 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. |
90 /// |
90 /// |
91 typedef typename Graph::template NodeMap<typename GR::Edge> PredMap; |
91 typedef typename Graph::template NodeMap<typename GR::Edge> PredMap; |
92 ///Instantiates a PredMap. |
92 ///Instantiates a PredMap. |
93 |
93 |
94 ///This function instantiates a \ref PredMap. |
94 ///This function instantiates a \ref PredMap. |
100 } |
100 } |
101 |
101 |
102 ///The type of the map that stores whether a nodes is processed. |
102 ///The type of the map that stores whether a nodes is processed. |
103 |
103 |
104 ///The type of the map that stores whether a nodes is processed. |
104 ///The type of the map that stores whether a nodes is processed. |
105 ///It must meet the \ref concept::WriteMap "WriteMap" concept. |
105 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. |
106 ///By default it is a NullMap. |
106 ///By default it is a NullMap. |
107 ///\todo If it is set to a real map, |
107 ///\todo If it is set to a real map, |
108 ///Dijkstra::processed() should read this. |
108 ///Dijkstra::processed() should read this. |
109 ///\todo named parameter to set this type, function to read and write. |
109 ///\todo named parameter to set this type, function to read and write. |
110 typedef NullMap<typename Graph::Node,bool> ProcessedMap; |
110 typedef NullMap<typename Graph::Node,bool> ProcessedMap; |
122 return new ProcessedMap(); |
122 return new ProcessedMap(); |
123 } |
123 } |
124 ///The type of the map that stores the dists of the nodes. |
124 ///The type of the map that stores the dists of the nodes. |
125 |
125 |
126 ///The type of the map that stores the dists of the nodes. |
126 ///The type of the map that stores the dists of the nodes. |
127 ///It must meet the \ref concept::WriteMap "WriteMap" concept. |
127 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. |
128 /// |
128 /// |
129 typedef typename Graph::template NodeMap<typename LM::Value> DistMap; |
129 typedef typename Graph::template NodeMap<typename LM::Value> DistMap; |
130 ///Instantiates a DistMap. |
130 ///Instantiates a DistMap. |
131 |
131 |
132 ///This function instantiates a \ref DistMap. |
132 ///This function instantiates a \ref DistMap. |
140 ///%Dijkstra algorithm class. |
140 ///%Dijkstra algorithm class. |
141 |
141 |
142 /// \ingroup flowalgs |
142 /// \ingroup flowalgs |
143 ///This class provides an efficient implementation of %Dijkstra algorithm. |
143 ///This class provides an efficient implementation of %Dijkstra algorithm. |
144 ///The edge lengths are passed to the algorithm using a |
144 ///The edge lengths are passed to the algorithm using a |
145 ///\ref concept::ReadMap "ReadMap", |
145 ///\ref concepts::ReadMap "ReadMap", |
146 ///so it is easy to change it to any kind of length. |
146 ///so it is easy to change it to any kind of length. |
147 /// |
147 /// |
148 ///The type of the length is determined by the |
148 ///The type of the length is determined by the |
149 ///\ref concept::ReadMap::Value "Value" of the length map. |
149 ///\ref concepts::ReadMap::Value "Value" of the length map. |
150 /// |
150 /// |
151 ///It is also possible to change the underlying priority heap. |
151 ///It is also possible to change the underlying priority heap. |
152 /// |
152 /// |
153 ///\param GR The graph type the algorithm runs on. The default value |
153 ///\param GR The graph type the algorithm runs on. The default value |
154 ///is \ref ListGraph. The value of GR is not used directly by |
154 ///is \ref ListGraph. The value of GR is not used directly by |
155 ///Dijkstra, it is only passed to \ref DijkstraDefaultTraits. |
155 ///Dijkstra, it is only passed to \ref DijkstraDefaultTraits. |
156 ///\param LM This read-only EdgeMap determines the lengths of the |
156 ///\param LM This read-only EdgeMap determines the lengths of the |
157 ///edges. It is read once for each edge, so the map may involve in |
157 ///edges. It is read once for each edge, so the map may involve in |
158 ///relatively time consuming process to compute the edge length if |
158 ///relatively time consuming process to compute the edge length if |
159 ///it is necessary. The default map type is \ref |
159 ///it is necessary. The default map type is \ref |
160 ///concept::Graph::EdgeMap "Graph::EdgeMap<int>". The value |
160 ///concepts::Graph::EdgeMap "Graph::EdgeMap<int>". The value |
161 ///of LM is not used directly by Dijkstra, it is only passed to \ref |
161 ///of LM is not used directly by Dijkstra, it is only passed to \ref |
162 ///DijkstraDefaultTraits. \param TR Traits class to set |
162 ///DijkstraDefaultTraits. \param TR Traits class to set |
163 ///various data types used by the algorithm. The default traits |
163 ///various data types used by the algorithm. The default traits |
164 ///class is \ref DijkstraDefaultTraits |
164 ///class is \ref DijkstraDefaultTraits |
165 ///"DijkstraDefaultTraits<GR,LM>". See \ref |
165 ///"DijkstraDefaultTraits<GR,LM>". See \ref |
817 ///The graph type the algorithm runs on. |
817 ///The graph type the algorithm runs on. |
818 typedef GR Graph; |
818 typedef GR Graph; |
819 ///The type of the map that stores the edge lengths. |
819 ///The type of the map that stores the edge lengths. |
820 |
820 |
821 ///The type of the map that stores the edge lengths. |
821 ///The type of the map that stores the edge lengths. |
822 ///It must meet the \ref concept::ReadMap "ReadMap" concept. |
822 ///It must meet the \ref concepts::ReadMap "ReadMap" concept. |
823 typedef LM LengthMap; |
823 typedef LM LengthMap; |
824 //The type of the length of the edges. |
824 //The type of the length of the edges. |
825 typedef typename LM::Value Value; |
825 typedef typename LM::Value Value; |
826 ///The heap type used by Dijkstra algorithm. |
826 ///The heap type used by Dijkstra algorithm. |
827 |
827 |
859 ///\brief The type of the map that stores the last |
859 ///\brief The type of the map that stores the last |
860 ///edges of the shortest paths. |
860 ///edges of the shortest paths. |
861 /// |
861 /// |
862 ///The type of the map that stores the last |
862 ///The type of the map that stores the last |
863 ///edges of the shortest paths. |
863 ///edges of the shortest paths. |
864 ///It must meet the \ref concept::WriteMap "WriteMap" concept. |
864 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. |
865 /// |
865 /// |
866 typedef NullMap <typename GR::Node,typename GR::Edge> PredMap; |
866 typedef NullMap <typename GR::Node,typename GR::Edge> PredMap; |
867 ///Instantiates a PredMap. |
867 ///Instantiates a PredMap. |
868 |
868 |
869 ///This function instantiates a \ref PredMap. |
869 ///This function instantiates a \ref PredMap. |
878 return new PredMap(); |
878 return new PredMap(); |
879 } |
879 } |
880 ///The type of the map that stores whether a nodes is processed. |
880 ///The type of the map that stores whether a nodes is processed. |
881 |
881 |
882 ///The type of the map that stores whether a nodes is processed. |
882 ///The type of the map that stores whether a nodes is processed. |
883 ///It must meet the \ref concept::WriteMap "WriteMap" concept. |
883 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. |
884 ///By default it is a NullMap. |
884 ///By default it is a NullMap. |
885 ///\todo If it is set to a real map, |
885 ///\todo If it is set to a real map, |
886 ///Dijkstra::processed() should read this. |
886 ///Dijkstra::processed() should read this. |
887 ///\todo named parameter to set this type, function to read and write. |
887 ///\todo named parameter to set this type, function to read and write. |
888 typedef NullMap<typename Graph::Node,bool> ProcessedMap; |
888 typedef NullMap<typename Graph::Node,bool> ProcessedMap; |
900 return new ProcessedMap(); |
900 return new ProcessedMap(); |
901 } |
901 } |
902 ///The type of the map that stores the dists of the nodes. |
902 ///The type of the map that stores the dists of the nodes. |
903 |
903 |
904 ///The type of the map that stores the dists of the nodes. |
904 ///The type of the map that stores the dists of the nodes. |
905 ///It must meet the \ref concept::WriteMap "WriteMap" concept. |
905 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. |
906 /// |
906 /// |
907 typedef NullMap<typename Graph::Node,typename LM::Value> DistMap; |
907 typedef NullMap<typename Graph::Node,typename LM::Value> DistMap; |
908 ///Instantiates a DistMap. |
908 ///Instantiates a DistMap. |
909 |
909 |
910 ///This function instantiates a \ref DistMap. |
910 ///This function instantiates a \ref DistMap. |