equal
deleted
inserted
replaced
19 |
19 |
20 ///\ingroup flowalgs |
20 ///\ingroup flowalgs |
21 ///\file |
21 ///\file |
22 ///\brief Dijkstra algorithm. |
22 ///\brief Dijkstra algorithm. |
23 /// |
23 /// |
24 ///\todo getPath() should be implemented! (also for BFS and DFS) |
|
25 ///\todo dijkstraZero() solution should be revised. |
24 ///\todo dijkstraZero() solution should be revised. |
26 |
25 |
27 #include <lemon/list_graph.h> |
26 #include <lemon/list_graph.h> |
28 #include <lemon/bin_heap.h> |
27 #include <lemon/bin_heap.h> |
29 #include <lemon/invalid.h> |
28 #include <lemon/invalid.h> |
244 ///Indicates if \ref _heap is locally allocated (\c true) or not. |
243 ///Indicates if \ref _heap is locally allocated (\c true) or not. |
245 bool local_heap; |
244 bool local_heap; |
246 |
245 |
247 ///Creates the maps if necessary. |
246 ///Creates the maps if necessary. |
248 |
247 |
249 ///\todo Error if \c G or are \c NULL. What about \c length? |
|
250 ///\todo Better memory allocation (instead of new). |
248 ///\todo Better memory allocation (instead of new). |
251 void create_maps() |
249 void create_maps() |
252 { |
250 { |
253 if(!_pred) { |
251 if(!_pred) { |
254 local_pred = true; |
252 local_pred = true; |
721 ///Copies the shortest path to \c t into \c p |
719 ///Copies the shortest path to \c t into \c p |
722 |
720 |
723 ///This function copies the shortest path to \c t into \c p. |
721 ///This function copies the shortest path to \c t into \c p. |
724 ///If it \c t is a source itself or unreachable, then it does not |
722 ///If it \c t is a source itself or unreachable, then it does not |
725 ///alter \c p. |
723 ///alter \c p. |
726 ///\todo Is it the right way to handle unreachable nodes? |
|
727 ///\return Returns \c true if a path to \c t was actually copied to \c p, |
724 ///\return Returns \c true if a path to \c t was actually copied to \c p, |
728 ///\c false otherwise. |
725 ///\c false otherwise. |
729 ///\sa DirPath |
726 ///\sa DirPath |
730 template<class P> |
727 template<class P> |
731 bool getPath(P &p,Node t) |
728 bool getPath(P &p,Node t) |
756 ///v. It is \ref INVALID |
753 ///v. It is \ref INVALID |
757 ///if \c v is unreachable from the root or if \c v=s. The |
754 ///if \c v is unreachable from the root or if \c v=s. The |
758 ///shortest path tree used here is equal to the shortest path tree used in |
755 ///shortest path tree used here is equal to the shortest path tree used in |
759 ///\ref predNode(). \pre \ref run() must be called before using |
756 ///\ref predNode(). \pre \ref run() must be called before using |
760 ///this function. |
757 ///this function. |
761 ///\todo predEdge could be a better name. |
|
762 Edge predEdge(Node v) const { return (*_pred)[v]; } |
758 Edge predEdge(Node v) const { return (*_pred)[v]; } |
763 |
759 |
764 ///Returns the 'previous node' of the shortest path tree. |
760 ///Returns the 'previous node' of the shortest path tree. |
765 |
761 |
766 ///For a node \c v it returns the 'previous node' of the shortest path tree, |
762 ///For a node \c v it returns the 'previous node' of the shortest path tree, |