41 ///\ref ReadMapSkeleton "readable map", |
45 ///\ref ReadMapSkeleton "readable map", |
42 ///so it is easy to change it to any kind of length. |
46 ///so it is easy to change it to any kind of length. |
43 /// |
47 /// |
44 ///The type of the length is determined by the \c ValueType of the length map. |
48 ///The type of the length is determined by the \c ValueType of the length map. |
45 /// |
49 /// |
46 ///It is also posible to change the underlying priority heap. |
50 ///It is also possible to change the underlying priority heap. |
47 /// |
51 /// |
48 ///\param Graph The graph type the algorithm runs on. |
52 ///\param Graph The graph type the algorithm runs on. |
49 ///\param LengthMap This read-only EdgeMap determines the |
53 ///\param LengthMap This read-only |
|
54 ///EdgeMap |
|
55 ///determines the |
50 ///lengths of the edges. It is read once for each edge, so the map |
56 ///lengths of the edges. It is read once for each edge, so the map |
51 ///may involve in relatively time consuming process to compute the edge |
57 ///may involve in relatively time consuming process to compute the edge |
52 ///length if it is necessary. |
58 ///length if it is necessary. The default map type is |
|
59 ///\ref GraphSkeleton::EdgeMap "Graph::EdgeMap<int>" |
53 ///\param Heap The heap type used by the %Dijkstra |
60 ///\param Heap The heap type used by the %Dijkstra |
54 ///algorithm. The default |
61 ///algorithm. The default |
55 ///is using \ref BinHeap "binary heap". |
62 ///is using \ref BinHeap "binary heap". |
|
63 |
|
64 #ifdef DOXYGEN |
|
65 template <typename Graph, |
|
66 typename LengthMap, |
|
67 typename Heap> |
|
68 #else |
56 template <typename Graph, |
69 template <typename Graph, |
57 typename LengthMap=typename Graph::EdgeMap<int>, |
70 typename LengthMap=typename Graph::EdgeMap<int>, |
58 typename Heap=BinHeap <typename Graph::Node, |
71 typename Heap=BinHeap <typename Graph::Node, |
59 typename LengthMap::ValueType, |
72 typename LengthMap::ValueType, |
60 typename Graph::NodeMap<int> > > |
73 typename Graph::NodeMap<int> > > |
|
74 #endif |
61 class Dijkstra{ |
75 class Dijkstra{ |
62 public: |
76 public: |
63 typedef typename Graph::Node Node; |
77 typedef typename Graph::Node Node; |
64 typedef typename Graph::NodeIt NodeIt; |
78 typedef typename Graph::NodeIt NodeIt; |
65 typedef typename Graph::Edge Edge; |
79 typedef typename Graph::Edge Edge; |
133 ///\pre \ref run() must be called before using this function. |
147 ///\pre \ref run() must be called before using this function. |
134 const PredNodeMap &predNodeMap() const { return pred_node;} |
148 const PredNodeMap &predNodeMap() const { return pred_node;} |
135 |
149 |
136 // bool reached(Node v) { return reach[v]; } |
150 // bool reached(Node v) { return reach[v]; } |
137 |
151 |
138 ///Chechs if a node is reachable from the source. |
152 ///Checks if a node is reachable from the source. |
139 |
153 |
140 ///Returns \c true if \c v is reachable from the source. |
154 ///Returns \c true if \c v is reachable from the source. |
141 ///\warning the source node is reported to be unreached! |
155 ///\warning the source node is reported to be unreached! |
142 ///\todo Is this what we want? |
156 ///\todo Is this what we want? |
143 ///\pre \ref run() must be called before using this function. |
157 ///\pre \ref run() must be called before using this function. |