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