equal
deleted
inserted
replaced
20 ///\ingroup flowalgs |
20 ///\ingroup flowalgs |
21 ///\file |
21 ///\file |
22 ///\brief Dijkstra algorithm. |
22 ///\brief Dijkstra algorithm. |
23 /// |
23 /// |
24 ///\todo getPath() should be implemented! (also for BFS and DFS) |
24 ///\todo getPath() should be implemented! (also for BFS and DFS) |
|
25 ///\todo dijkstraZero() solution should be revised. |
25 |
26 |
26 #include <lemon/list_graph.h> |
27 #include <lemon/list_graph.h> |
27 #include <lemon/bin_heap.h> |
28 #include <lemon/bin_heap.h> |
28 #include <lemon/invalid.h> |
29 #include <lemon/invalid.h> |
29 #include <lemon/error.h> |
30 #include <lemon/error.h> |
30 #include <lemon/maps.h> |
31 #include <lemon/maps.h> |
31 |
32 |
32 namespace lemon { |
33 namespace lemon { |
33 |
34 |
34 |
35 template<class T> T dijkstraZero() {return 0;} |
35 |
36 |
36 ///Default traits class of Dijkstra class. |
37 ///Default traits class of Dijkstra class. |
37 |
38 |
38 ///Default traits class of Dijkstra class. |
39 ///Default traits class of Dijkstra class. |
39 ///\param GR Graph type. |
40 ///\param GR Graph type. |
497 ///The optional second parameter is the initial distance of the node. |
498 ///The optional second parameter is the initial distance of the node. |
498 /// |
499 /// |
499 ///It checks if the node has already been added to the heap and |
500 ///It checks if the node has already been added to the heap and |
500 ///It is pushed to the heap only if either it was not in the heap |
501 ///It is pushed to the heap only if either it was not in the heap |
501 ///or the shortest path found till then is longer then \c dst. |
502 ///or the shortest path found till then is longer then \c dst. |
502 void addSource(Node s,Value dst=0) |
503 void addSource(Node s,Value dst=dijkstraZero<Value>()) |
503 { |
504 { |
504 if(_heap->state(s) != Heap::IN_HEAP) { |
505 if(_heap->state(s) != Heap::IN_HEAP) { |
505 _heap->push(s,dst); |
506 _heap->push(s,dst); |
506 } else if((*_heap)[s]<dst) { |
507 } else if((*_heap)[s]<dst) { |
507 _heap->push(s,dst); |
508 _heap->push(s,dst); |
657 ///\endcode |
658 ///\endcode |
658 Value run(Node s,Node t) { |
659 Value run(Node s,Node t) { |
659 init(); |
660 init(); |
660 addSource(s); |
661 addSource(s); |
661 start(t); |
662 start(t); |
662 return (*_pred)[t]==INVALID?0:(*_dist)[t]; |
663 return (*_pred)[t]==INVALID?dijkstraZero<Value>():(*_dist)[t]; |
663 } |
664 } |
664 |
665 |
665 ///@} |
666 ///@} |
666 |
667 |
667 ///\name Query Functions |
668 ///\name Query Functions |
744 ///Returns \c true if \c v is reachable from the root. |
745 ///Returns \c true if \c v is reachable from the root. |
745 ///\warning The source nodes are inditated as unreached. |
746 ///\warning The source nodes are inditated as unreached. |
746 ///\pre \ref run() must be called before using this function. |
747 ///\pre \ref run() must be called before using this function. |
747 /// |
748 /// |
748 bool reached(Node v) { return (*_heap_cross_ref)[v] != Heap::PRE_HEAP; } |
749 bool reached(Node v) { return (*_heap_cross_ref)[v] != Heap::PRE_HEAP; } |
|
750 |
|
751 ///Checks if a node is processed. |
|
752 |
|
753 ///Returns \c true if \c v is processed, i.e. the shortest |
|
754 ///path to \c v has already found. |
|
755 ///\pre \ref run() must be called before using this function. |
|
756 /// |
|
757 bool processed(Node v) { return (*_heap_cross_ref)[v] == Heap::POST_HEAP; } |
749 |
758 |
750 ///@} |
759 ///@} |
751 }; |
760 }; |
752 |
761 |
753 |
762 |