Changeset 286:da414906fe21 in lemon for lemon/dijkstra.h
 Timestamp:
 09/26/08 12:40:11 (11 years ago)
 Branch:
 default
 Phase:
 public
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

lemon/dijkstra.h
r278 r286 729 729 } 730 730 731 ///Executes the algorithm until the given target node is reached.732 733 ///Executes the algorithm until the given target node is reached.731 ///Executes the algorithm until the given target node is processed. 732 733 ///Executes the algorithm until the given target node is processed. 734 734 /// 735 735 ///This method runs the %Dijkstra algorithm from the root node(s) 736 ///in order to compute the shortest path to \c dest.736 ///in order to compute the shortest path to \c t. 737 737 /// 738 738 ///The algorithm computes 739 /// the shortest path to \c dest,740 /// the distance of \c dest from the root(s).739 /// the shortest path to \c t, 740 /// the distance of \c t from the root(s). 741 741 /// 742 742 ///\pre init() must be called and at least one root node should be 743 743 ///added with addSource() before using this function. 744 void start(Node dest) 745 { 746 while ( !_heap>empty() && _heap>top()!=dest ) processNextNode(); 747 if ( !_heap>empty() ) finalizeNodeData(_heap>top(),_heap>prio()); 744 void start(Node t) 745 { 746 while ( !_heap>empty() && _heap>top()!=t ) processNextNode(); 747 if ( !_heap>empty() ) { 748 finalizeNodeData(_heap>top(),_heap>prio()); 749 _heap>pop(); 750 } 748 751 } 749 752 … … 773 776 } 774 777 775 ///Runs the algorithm from the given node.778 ///Runs the algorithm from the given source node. 776 779 777 780 ///This method runs the %Dijkstra algorithm from node \c s … … 797 800 798 801 ///This method runs the %Dijkstra algorithm from node \c s 799 ///in order to compute the shortest path to \c t.800 /// 801 /// \return The length of the shortest <tt>s</tt><tt>t</tt> path,802 /// if \c t is reachable form \c s, \c 0 otherwise.802 ///in order to compute the shortest path to node \c t 803 ///(it stops searching when \c t is processed). 804 /// 805 ///\return \c true if \c t is reachable form \c s. 803 806 /// 804 807 ///\note Apart from the return value, <tt>d.run(s,t)</tt> is just a … … 809 812 /// d.start(t); 810 813 ///\endcode 811 Valuerun(Node s,Node t) {814 bool run(Node s,Node t) { 812 815 init(); 813 816 addSource(s); 814 817 start(t); 815 return (*_ pred)[t]==INVALID?OperationTraits::zero():(*_dist)[t];818 return (*_heap_cross_ref)[t] == Heap::POST_HEAP; 816 819 } 817 820 … … 909 912 ///Returns \c true if \c v is processed, i.e. the shortest 910 913 ///path to \c v has already found. 911 ///\pre Either \ref run() or \ref start()914 ///\pre Either \ref run() or \ref init() 912 915 ///must be called before using this function. 913 916 bool processed(Node v) const { return (*_heap_cross_ref)[v] == … … 918 921 ///Returns the current distance of a node from the root(s). 919 922 ///It may be decreased in the following processes. 920 ///\pre \c v should be reached but not processed. 921 Value currentDist(Node v) const { return (*_heap)[v]; } 923 ///\pre Either \ref run() or \ref init() 924 ///must be called before using this function and 925 ///node \c v must be reached but not necessarily processed. 926 Value currentDist(Node v) const { 927 return processed(v) ? (*_dist)[v] : (*_heap)[v]; 928 } 922 929 923 930 ///@}
Note: See TracChangeset
for help on using the changeset viewer.