726 void start() |
726 void start() |
727 { |
727 { |
728 while ( !emptyQueue() ) processNextNode(); |
728 while ( !emptyQueue() ) processNextNode(); |
729 } |
729 } |
730 |
730 |
731 ///Executes the algorithm until the given target node is reached. |
731 ///Executes the algorithm until the given target node is processed. |
732 |
732 |
733 ///Executes the algorithm until the given target node is reached. |
733 ///Executes the algorithm until the given target node is processed. |
734 /// |
734 /// |
735 ///This method runs the %Dijkstra algorithm from the root node(s) |
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 ///The algorithm computes |
738 ///The algorithm computes |
739 ///- the shortest path to \c dest, |
739 ///- the shortest path to \c t, |
740 ///- the distance of \c dest from the root(s). |
740 ///- the distance of \c t from the root(s). |
741 /// |
741 /// |
742 ///\pre init() must be called and at least one root node should be |
742 ///\pre init() must be called and at least one root node should be |
743 ///added with addSource() before using this function. |
743 ///added with addSource() before using this function. |
744 void start(Node dest) |
744 void start(Node t) |
745 { |
745 { |
746 while ( !_heap->empty() && _heap->top()!=dest ) processNextNode(); |
746 while ( !_heap->empty() && _heap->top()!=t ) processNextNode(); |
747 if ( !_heap->empty() ) finalizeNodeData(_heap->top(),_heap->prio()); |
747 if ( !_heap->empty() ) { |
|
748 finalizeNodeData(_heap->top(),_heap->prio()); |
|
749 _heap->pop(); |
|
750 } |
748 } |
751 } |
749 |
752 |
750 ///Executes the algorithm until a condition is met. |
753 ///Executes the algorithm until a condition is met. |
751 |
754 |
752 ///Executes the algorithm until a condition is met. |
755 ///Executes the algorithm until a condition is met. |
770 if ( _heap->empty() ) return INVALID; |
773 if ( _heap->empty() ) return INVALID; |
771 finalizeNodeData(_heap->top(),_heap->prio()); |
774 finalizeNodeData(_heap->top(),_heap->prio()); |
772 return _heap->top(); |
775 return _heap->top(); |
773 } |
776 } |
774 |
777 |
775 ///Runs the algorithm from the given node. |
778 ///Runs the algorithm from the given source node. |
776 |
779 |
777 ///This method runs the %Dijkstra algorithm from node \c s |
780 ///This method runs the %Dijkstra algorithm from node \c s |
778 ///in order to compute the shortest path to each node. |
781 ///in order to compute the shortest path to each node. |
779 /// |
782 /// |
780 ///The algorithm computes |
783 ///The algorithm computes |
794 } |
797 } |
795 |
798 |
796 ///Finds the shortest path between \c s and \c t. |
799 ///Finds the shortest path between \c s and \c t. |
797 |
800 |
798 ///This method runs the %Dijkstra algorithm from node \c s |
801 ///This method runs the %Dijkstra algorithm from node \c s |
799 ///in order to compute the shortest path to \c t. |
802 ///in order to compute the shortest path to node \c t |
800 /// |
803 ///(it stops searching when \c t is processed). |
801 ///\return The length of the shortest <tt>s</tt>--<tt>t</tt> path, |
804 /// |
802 ///if \c t is reachable form \c s, \c 0 otherwise. |
805 ///\return \c true if \c t is reachable form \c s. |
803 /// |
806 /// |
804 ///\note Apart from the return value, <tt>d.run(s,t)</tt> is just a |
807 ///\note Apart from the return value, <tt>d.run(s,t)</tt> is just a |
805 ///shortcut of the following code. |
808 ///shortcut of the following code. |
806 ///\code |
809 ///\code |
807 /// d.init(); |
810 /// d.init(); |
808 /// d.addSource(s); |
811 /// d.addSource(s); |
809 /// d.start(t); |
812 /// d.start(t); |
810 ///\endcode |
813 ///\endcode |
811 Value run(Node s,Node t) { |
814 bool run(Node s,Node t) { |
812 init(); |
815 init(); |
813 addSource(s); |
816 addSource(s); |
814 start(t); |
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 |
818 ///@} |
821 ///@} |
819 |
822 |
820 ///\name Query Functions |
823 ///\name Query Functions |
906 |
909 |
907 ///Checks if a node is processed. |
910 ///Checks if a node is processed. |
908 |
911 |
909 ///Returns \c true if \c v is processed, i.e. the shortest |
912 ///Returns \c true if \c v is processed, i.e. the shortest |
910 ///path to \c v has already found. |
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 ///must be called before using this function. |
915 ///must be called before using this function. |
913 bool processed(Node v) const { return (*_heap_cross_ref)[v] == |
916 bool processed(Node v) const { return (*_heap_cross_ref)[v] == |
914 Heap::POST_HEAP; } |
917 Heap::POST_HEAP; } |
915 |
918 |
916 ///The current distance of a node from the root(s). |
919 ///The current distance of a node from the root(s). |
917 |
920 |
918 ///Returns the current distance of a node from the root(s). |
921 ///Returns the current distance of a node from the root(s). |
919 ///It may be decreased in the following processes. |
922 ///It may be decreased in the following processes. |
920 ///\pre \c v should be reached but not processed. |
923 ///\pre Either \ref run() or \ref init() |
921 Value currentDist(Node v) const { return (*_heap)[v]; } |
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 ///@} |
924 }; |
931 }; |
925 |
932 |
926 |
933 |