equal
deleted
inserted
replaced
18 #define LEMON_DIJKSTRA_H |
18 #define LEMON_DIJKSTRA_H |
19 |
19 |
20 ///\ingroup flowalgs |
20 ///\ingroup flowalgs |
21 ///\file |
21 ///\file |
22 ///\brief Dijkstra algorithm. |
22 ///\brief Dijkstra algorithm. |
|
23 /// |
|
24 ///\todo getPath() should be implemented! (also for BFS and DFS) |
23 |
25 |
24 #include <lemon/list_graph.h> |
26 #include <lemon/list_graph.h> |
25 #include <lemon/bin_heap.h> |
27 #include <lemon/bin_heap.h> |
26 #include <lemon/invalid.h> |
28 #include <lemon/invalid.h> |
27 #include <lemon/error.h> |
29 #include <lemon/error.h> |
653 ///Before the use of these functions, |
655 ///Before the use of these functions, |
654 ///either run() or start() must be called. |
656 ///either run() or start() must be called. |
655 |
657 |
656 ///@{ |
658 ///@{ |
657 |
659 |
|
660 ///Copies the shortest path to \c t into \c p |
|
661 |
|
662 ///This function copies the shortest path to \c t into \c p. |
|
663 ///If it \c \t is a source itself or unreachable, then it does not |
|
664 ///alter \c p. |
|
665 ///\todo Is it the right way to handle unreachable nodes? |
|
666 ///\return Returns \c true if a path to \c t was actually copied to \c p, |
|
667 ///\c false otherwise. |
|
668 ///\sa DirPath |
|
669 template<class P> |
|
670 bool getPath(P &p,Node t) |
|
671 { |
|
672 if(reached(t)) { |
|
673 p.clear(); |
|
674 typename P::Builder b(p); |
|
675 for(b.setStartNode(t);pred(t)!=INVALID;t=predNode(t)) |
|
676 b.pushFront(pred(t)); |
|
677 b.commit(); |
|
678 return true; |
|
679 } |
|
680 return false; |
|
681 } |
|
682 |
658 ///The distance of a node from the root. |
683 ///The distance of a node from the root. |
659 |
684 |
660 ///Returns the distance of a node from the root. |
685 ///Returns the distance of a node from the root. |
661 ///\pre \ref run() must be called before using this function. |
686 ///\pre \ref run() must be called before using this function. |
662 ///\warning If node \c v in unreachable from the root the return value |
687 ///\warning If node \c v in unreachable from the root the return value |