# HG changeset patch
# User deba
# Date 1130490119 0
# Node ID bccf2379b5dd9272f52a69c5275ad33af6f0d05f
# Parent  874e4bc21435b235b33af29a0c4a16b8c0443992
Faster implementation

diff -r 874e4bc21435 -r bccf2379b5dd lemon/johnson.h
--- a/lemon/johnson.h	Fri Oct 28 08:40:42 2005 +0000
+++ b/lemon/johnson.h	Fri Oct 28 09:01:59 2005 +0000
@@ -494,14 +494,16 @@
 
     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);