Changes in lemon/dijkstra.h [287:bb40b6db0a58:281:e9b4fbe163f5] in lemon-1.0
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/dijkstra.h
r287 r281 725 725 } 726 726 727 ///Executes the algorithm until the given target node is processed.728 729 ///Executes the algorithm until the given target node is processed.727 ///Executes the algorithm until the given target node is reached. 728 729 ///Executes the algorithm until the given target node is reached. 730 730 /// 731 731 ///This method runs the %Dijkstra algorithm from the root node(s) 732 ///in order to compute the shortest path to \c t.732 ///in order to compute the shortest path to \c dest. 733 733 /// 734 734 ///The algorithm computes 735 ///- the shortest path to \c t,736 ///- the distance of \c t from the root(s).735 ///- the shortest path to \c dest, 736 ///- the distance of \c dest from the root(s). 737 737 /// 738 738 ///\pre init() must be called and at least one root node should be 739 739 ///added with addSource() before using this function. 740 void start(Node t) 741 { 742 while ( !_heap->empty() && _heap->top()!=t ) processNextNode(); 743 if ( !_heap->empty() ) { 744 finalizeNodeData(_heap->top(),_heap->prio()); 745 _heap->pop(); 746 } 740 void start(Node dest) 741 { 742 while ( !_heap->empty() && _heap->top()!=dest ) processNextNode(); 743 if ( !_heap->empty() ) finalizeNodeData(_heap->top(),_heap->prio()); 747 744 } 748 745 … … 772 769 } 773 770 774 ///Runs the algorithm from the given sourcenode.771 ///Runs the algorithm from the given node. 775 772 776 773 ///This method runs the %Dijkstra algorithm from node \c s … … 796 793 797 794 ///This method runs the %Dijkstra algorithm from node \c s 798 ///in order to compute the shortest path to node \c t799 /// (it stops searching when \c t is processed).800 /// 801 /// \return \c true if \c t is reachable form \c s.795 ///in order to compute the shortest path to \c t. 796 /// 797 ///\return The length of the shortest <tt>s</tt>--<tt>t</tt> path, 798 ///if \c t is reachable form \c s, \c 0 otherwise. 802 799 /// 803 800 ///\note Apart from the return value, <tt>d.run(s,t)</tt> is just a … … 808 805 /// d.start(t); 809 806 ///\endcode 810 boolrun(Node s,Node t) {807 Value run(Node s,Node t) { 811 808 init(); 812 809 addSource(s); 813 810 start(t); 814 return (*_ heap_cross_ref)[t] == Heap::POST_HEAP;811 return (*_pred)[t]==INVALID?OperationTraits::zero():(*_dist)[t]; 815 812 } 816 813 … … 908 905 ///Returns \c true if \c v is processed, i.e. the shortest 909 906 ///path to \c v has already found. 910 ///\pre Either \ref run() or \ref init()907 ///\pre Either \ref run() or \ref start() 911 908 ///must be called before using this function. 912 909 bool processed(Node v) const { return (*_heap_cross_ref)[v] == … … 917 914 ///Returns the current distance of a node from the root(s). 918 915 ///It may be decreased in the following processes. 919 ///\pre Either \ref run() or \ref init() 920 ///must be called before using this function and 921 ///node \c v must be reached but not necessarily processed. 922 Value currentDist(Node v) const { 923 return processed(v) ? (*_dist)[v] : (*_heap)[v]; 924 } 916 ///\pre \c v should be reached but not processed. 917 Value currentDist(Node v) const { return (*_heap)[v]; } 925 918 926 919 ///@}
Note: See TracChangeset
for help on using the changeset viewer.