Changeset 1155:fe0fcdb5687b in lemon-0.x for src/lemon/dijkstra.h

Timestamp:

02/18/05 15:46:04 (20 years ago)

Author:

Alpar Juttner

Branch:

default

Phase:

public

Convert:

svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1556

Message:

• Better addSource()
• More docs

File:

• src/lemon/dijkstra.h (modified) (2 diffs)

src/lemon/dijkstra.h

@@ -484 +484 @@
     ///Adds a new source node.
 
-    ///Adds a new source node the the priority heap.
-    ///It checks if the node has already been added to the heap.
+    ///Adds a new source node to the priority heap.
     ///
     ///The optional second parameter is the initial distance of the node.
     ///
-    ///\todo Do we really want to check it?
+    ///It checks if the node has already been added to the heap and
+    ///It is pushed to the heap only if either it was not in the heap
+    ///or the shortest path found till then is longer then \c dst.
     void addSource(Node s,Value dst=0)
     {
       source = s;
       if(_heap.state(s) != Heap::IN_HEAP) _heap.push(s,dst);
-    }
-    
+      else if(_heap[s]<dst) {
+        _heap.push(s,dst);
+        _pred->set(s,INVALID);
+      }
+    }
+    
+    ///Processes the next node in the priority heap
+
+    ///Processes the next node in the priority heap.
+    ///
+    ///\warning The priority heap must not be empty!
     void processNextNode()
     {
@@ -524 +534 @@
     }
 
+    ///Returns \c false if there are nodes to be processed in the priority heap
+
+    ///Returns \c false if there are nodes to be processed in the priority heap
+    ///
+    bool emptyHeap() { return heap.empty(); }
+    ///Returns the number of the nodes to be processed in the priority heap
+
+    ///Returns the number of the nodes to be processed in the priority heap
+    ///
+    int heapSize() { return heap.size(); }
+    
     ///Executes the algorithm.