25 /// |
25 /// |
26 ///\todo dijkstraZero() solution should be revised. |
26 ///\todo dijkstraZero() solution should be revised. |
27 |
27 |
28 #include <lemon/list_graph.h> |
28 #include <lemon/list_graph.h> |
29 #include <lemon/bin_heap.h> |
29 #include <lemon/bin_heap.h> |
|
30 #include <lemon/bits/path_dump.h> |
30 #include <lemon/bits/invalid.h> |
31 #include <lemon/bits/invalid.h> |
31 #include <lemon/error.h> |
32 #include <lemon/error.h> |
32 #include <lemon/maps.h> |
33 #include <lemon/maps.h> |
|
34 |
33 |
35 |
34 namespace lemon { |
36 namespace lemon { |
35 |
37 |
36 template<class T> T dijkstraZero() {return 0;} |
38 template<class T> T dijkstraZero() {return 0;} |
37 |
39 |
715 ///Before the use of these functions, |
717 ///Before the use of these functions, |
716 ///either run() or start() must be called. |
718 ///either run() or start() must be called. |
717 |
719 |
718 ///@{ |
720 ///@{ |
719 |
721 |
720 ///Copies the shortest path to \c t into \c p |
722 typedef PredMapPath<Graph, PredMap> Path; |
721 |
723 |
722 ///This function copies the shortest path to \c t into \c p. |
724 ///Gives back the shortest path. |
723 ///If it \c t is a source itself or unreachable, then it does not |
725 |
724 ///alter \c p. |
726 ///Gives back the shortest path. |
725 ///\return Returns \c true if a path to \c t was actually copied to \c p, |
727 ///\pre The \c t should be reachable from the source. |
726 ///\c false otherwise. |
728 Path path(Node t) |
727 ///\sa DirPath |
729 { |
728 template<class P> |
730 return Path(*G, *_pred, t); |
729 bool getPath(P &p,Node t) |
731 } |
730 { |
732 |
731 if(reached(t)) { |
|
732 p.clear(); |
|
733 typename P::Builder b(p); |
|
734 for(b.setStartNode(t);predEdge(t)!=INVALID;t=predNode(t)) |
|
735 b.pushFront(predEdge(t)); |
|
736 b.commit(); |
|
737 return true; |
|
738 } |
|
739 return false; |
|
740 } |
|
741 |
|
742 ///The distance of a node from the root. |
733 ///The distance of a node from the root. |
743 |
734 |
744 ///Returns the distance of a node from the root. |
735 ///Returns the distance of a node from the root. |
745 ///\pre \ref run() must be called before using this function. |
736 ///\pre \ref run() must be called before using this function. |
746 ///\warning If node \c v in unreachable from the root the return value |
737 ///\warning If node \c v in unreachable from the root the return value |