21 /// |
19 /// |
22 ///The type of the length is determined by the \c ValueType of the length map. |
20 ///The type of the length is determined by the \c ValueType of the length map. |
23 /// |
21 /// |
24 ///It is also possible to change the underlying priority heap. |
22 ///It is also possible to change the underlying priority heap. |
25 /// |
23 /// |
26 ///\param Graph The graph type the algorithm runs on. |
24 ///\param Graph The graph type the algorithm runs on. |
27 ///\param LengthMap This read-only EdgeMap determines the lengths of |
25 ///\param LengthMap This read-only |
28 ///the edges. It is read once for each edge, so the map may involve |
26 ///EdgeMap |
29 ///in relatively time consuming process to compute the edge length |
27 ///determines the |
30 ///if it is necessary. The default map type is \ref |
28 ///lengths of the edges. It is read once for each edge, so the map |
31 ///GraphSkeleton::EdgeMap "Graph::EdgeMap<int>" |
29 ///may involve in relatively time consuming process to compute the edge |
32 ///\param Heap The heap type used by the %Dijkstra algorithm. The |
30 ///length if it is necessary. The default map type is |
33 ///default is using \ref BinHeap "binary heap". |
31 ///\ref GraphSkeleton::EdgeMap "Graph::EdgeMap<int>" |
|
32 ///\param Heap The heap type used by the %Dijkstra |
|
33 ///algorithm. The default |
|
34 ///is using \ref BinHeap "binary heap". |
34 |
35 |
35 #ifdef DOXYGEN |
36 #ifdef DOXYGEN |
36 template <typename Graph, |
37 template <typename Graph, |
37 typename LengthMap, |
38 typename LengthMap, |
38 typename Heap> |
39 typename Heap> |
65 Dijkstra(Graph& _G, LengthMap& _length) : |
66 Dijkstra(Graph& _G, LengthMap& _length) : |
66 G(_G), length(_length), predecessor(_G), pred_node(_G), distance(_G) { } |
67 G(_G), length(_length), predecessor(_G), pred_node(_G), distance(_G) { } |
67 |
68 |
68 void run(Node s); |
69 void run(Node s); |
69 |
70 |
70 ///The distance of a node from the source. |
71 ///The distance of a node from the root. |
71 |
72 |
72 ///Returns the distance of a node from the source. |
73 ///Returns the distance of a node from the root. |
73 ///\pre \ref run() must be called before using this function. |
74 ///\pre \ref run() must be called before using this function. |
74 ///\warning If node \c v in unreachable from the source the return value |
75 ///\warning If node \c v in unreachable from the root the return value |
75 ///of this funcion is undefined. |
76 ///of this funcion is undefined. |
76 ValueType dist(Node v) const { return distance[v]; } |
77 ValueType dist(Node v) const { return distance[v]; } |
77 |
78 |
78 ///Returns the edges of the shortest path tree. |
79 ///Returns the previous edge of the shortest path tree. |
79 |
80 |
80 ///For a node \c v it returns the last edge of the shortest path |
81 ///For a node \c v it returns the previous edge of the shortest path tree, |
81 ///from the source to \c v or INVALID if \c v is unreachable |
82 ///i.e. it returns the last edge from a shortest path from the root to \c |
82 ///from the source. |
83 ///v. It is INVALID if \c v is unreachable from the root or if \c v=s. The |
83 ///\pre \ref run() must be called before using this function. |
84 ///shortest path tree used here is equal to the shortest path tree used in |
|
85 ///\ref predNode(Node v). \pre \ref run() must be called before using |
|
86 ///this function. |
84 Edge pred(Node v) const { return predecessor[v]; } |
87 Edge pred(Node v) const { return predecessor[v]; } |
85 |
88 |
86 ///Returns the nodes of the shortest paths. |
89 ///Returns the previous node of the shortest path tree. |
87 |
90 |
88 ///For a node \c v it returns the last but one node of the shortest path |
91 ///For a node \c v it returns the previous node of the shortest path tree, |
89 ///from the source to \c v or INVALID if \c v is unreachable |
92 ///i.e. it returns the last but one node from a shortest path from the |
90 ///from the source. |
93 ///root to \c /v. It is INVALID if \c v is unreachable from the root or if |
91 ///\pre \ref run() must be called before using this function. |
94 ///\c v=s. The shortest path tree used here is equal to the shortest path |
|
95 ///tree used in \ref pred(Node v). \pre \ref run() must be called before |
|
96 ///using this function. |
92 Node predNode(Node v) const { return pred_node[v]; } |
97 Node predNode(Node v) const { return pred_node[v]; } |
93 |
98 |
94 ///Returns a reference to the NodeMap of distances. |
99 ///Returns a reference to the NodeMap of distances. |
95 |
100 |
96 ///\pre \ref run() must be called before using this function. |
101 ///Returns a reference to the NodeMap of distances. \pre \ref run() must |
97 /// |
102 ///be called before using this function. |
98 const DistMap &distMap() const { return distance;} |
103 const DistMap &distMap() const { return distance;} |
99 |
104 |
100 ///Returns a reference to the shortest path tree map. |
105 ///Returns a reference to the shortest path tree map. |
101 |
106 |
102 ///Returns a reference to the NodeMap of the edges of the |
107 ///Returns a reference to the NodeMap of the edges of the |
103 ///shortest path tree. |
108 ///shortest path tree. |
104 ///\pre \ref run() must be called before using this function. |
109 ///\pre \ref run() must be called before using this function. |
105 const PredMap &predMap() const { return predecessor;} |
110 const PredMap &predMap() const { return predecessor;} |
106 |
111 |
107 ///Returns a reference to the map of nodes of shortest paths. |
112 ///Returns a reference to the map of nodes of shortest paths. |
108 |
113 |
109 ///Returns a reference to the NodeMap of the last but one nodes of the |
114 ///Returns a reference to the NodeMap of the last but one nodes of the |
110 ///shortest paths. |
115 ///shortest path tree. |
111 ///\pre \ref run() must be called before using this function. |
116 ///\pre \ref run() must be called before using this function. |
112 const PredNodeMap &predNodeMap() const { return pred_node;} |
117 const PredNodeMap &predNodeMap() const { return pred_node;} |
113 |
118 |
114 ///Checks if a node is reachable from the source. |
119 ///Checks if a node is reachable from the root. |
115 |
120 |
116 ///Returns \c true if \c v is reachable from the source. |
121 ///Returns \c true if \c v is reachable from the root. |
117 ///\warning the source node is reported to be unreached! |
122 ///\warning the root node is reported to be unreached! |
118 ///\todo Is this what we want? |
123 ///\todo Is this what we want? |
119 ///\pre \ref run() must be called before using this function. |
124 ///\pre \ref run() must be called before using this function. |
|
125 /// |
120 bool reached(Node v) { return G.valid(predecessor[v]); } |
126 bool reached(Node v) { return G.valid(predecessor[v]); } |
121 |
127 |
122 }; |
128 }; |
123 |
129 |
124 |
130 |
125 // ********************************************************************** |
131 // ********************************************************************** |
126 // IMPLEMENTATIONS |
132 // IMPLEMENTATIONS |
127 // ********************************************************************** |
133 // ********************************************************************** |
128 |
134 |
129 ///Runs %Dijkstra algorithm from source node \c s. |
135 ///Runs %Dijkstra algorithm from node the root. |
130 |
136 |
131 ///This method runs the %Dijkstra algorithm from a source node \c s |
137 ///This method runs the %Dijkstra algorithm from a root node \c s |
132 ///in order to compute the shortest path to each node. The algorithm |
138 ///in order to |
133 ///computes - The shortest path tree. - The distance of each node |
139 ///compute the |
134 ///from the source. |
140 ///shortest path to each node. The algorithm computes |
|
141 ///- The shortest path tree. |
|
142 ///- The distance of each node from the root. |
135 template <typename Graph, typename LengthMap, |
143 template <typename Graph, typename LengthMap, |
136 template<class,class,class> class Heap > |
144 template<class,class,class> class Heap > |
137 void Dijkstra<Graph,LengthMap,Heap>::run(Node s) { |
145 void Dijkstra<Graph,LengthMap,Heap>::run(Node s) { |
138 |
146 |
139 NodeIt u; |
147 NodeIt u; |