Changeset 1747:bccf2379b5dd in lemon-0.x

Timestamp:

10/28/05 11:01:59 (18 years ago)

Author:

Balazs Dezso

Branch:

default

Phase:

public

Convert:

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

Message:

Faster implementation

File:

• lemon/johnson.h (modified) (1 diff)

lemon/johnson.h

@@ -495 +495 @@
     void shiftedRun(const BelmannFordType& belmannford) {
       
-      typedef PotentialDifferenceMap<Graph, 
-      typename BelmannFordType::DistMap> PotDiffMap;
-      PotDiffMap potdiff(*graph, belmannford.distMap());
-      typedef SubMap<LengthMap, PotDiffMap> ShiftLengthMap;
-      ShiftLengthMap shiftlen(*length, potdiff);
-
-      typename Dijkstra<Graph, ShiftLengthMap>::
-      template DefHeap<Heap, HeapCrossRef>::Create dijkstra(*graph, shiftlen);
+      typename Graph::template EdgeMap<Value> shiftlen(*graph);
+      for (EdgeIt it(*graph);  it != INVALID; ++it) {
+        shiftlen[it] = (*length)[it] 
+          + belmannford.dist(graph->source(it)) 
+          - belmannford.dist(graph->target(it));
+      }
+      
+      typename Dijkstra<Graph, typename Graph::template EdgeMap<Value> >::
+        template DefHeap<Heap, HeapCrossRef>::
+        Create dijkstra(*graph, shiftlen);
 
       dijkstra.heap(*_heap, *_heap_cross_ref);