Index: branches/RoutePlanning/HeuristicLab.Algorithms.GraphRouting/3.3/AStarAlgorithmV3.cs
===================================================================
--- branches/RoutePlanning/HeuristicLab.Algorithms.GraphRouting/3.3/AStarAlgorithmV3.cs	(revision 8631)
+++ branches/RoutePlanning/HeuristicLab.Algorithms.GraphRouting/3.3/AStarAlgorithmV3.cs	(revision 8640)
@@ -4,7 +4,9 @@
 using HeuristicLab.Algorithms.GraphRouting.Interfaces;
 using HeuristicLab.Problems.RoutePlanning.Interfaces;
+using HeuristicLab.Problems.RoutePlanning.RoutingGraph;
 namespace HeuristicLab.Algorithms.GraphRouting {
   public class AStarAlgorithmV3 : IRouter {
     private IGraph graph;
+    private ICostCalculator costCalculator;
 
     private Dictionary<long, float> distances;
@@ -15,6 +17,11 @@
     private Dictionary<long, NodeData> openListLookup;
 
-    public AStarAlgorithmV3(IGraph graph) {
+    public AStarAlgorithmV3(IGraph graph)
+      : this(graph, new TravelTimeCostCalculator()) {
+    }
+
+    public AStarAlgorithmV3(IGraph graph, ICostCalculator costCalc) {
       this.graph = graph;
+      this.costCalculator = costCalc;
     }
 
@@ -36,12 +43,23 @@
       distances.Add(currentNode, 0);
 
+      int i = 0;
       while (openList.Count > 0) {
+
         NodeData data = openList.Min;
+        //Console.Write(i + ": (" + openList.Count + "/");
         openList.Remove(data);
+        //Console.Write(openList.Count + ") - (" + openListLookup.Count + "/");
         openListLookup.Remove(data.Node);
+        //Console.WriteLine(openListLookup.Count + ")");
         currentNode = data.Node;
         if (currentNode == targetNodeId) {
           return ReconstructPath(currentNode).ToArray();
         }
+
+        //if (openList.Count != openListLookup.Count) {
+        //  Console.WriteLine();
+        //} else {
+        //  Console.Write(".");
+        //}
 
         Dictionary<long, float> currentNeighbors = graph.GetNeighborsWithWeight(currentNode);
@@ -58,5 +76,7 @@
           predecessors[neighbor.Key] = currentNode;
 
-          float f = costsFromStart + graph.EstimatedCosts(neighbor.Key, targetNodeId);
+          Vertex vertNeigh = graph.GetVertex(neighbor.Key);
+          Vertex vertTarget = graph.GetVertex(targetNodeId);
+          float f = costsFromStart + costCalculator.EstimatedCosts(vertNeigh, vertTarget);
 
           if (openListLookup.ContainsKey(neighbor.Key)) {
@@ -66,9 +86,10 @@
 
           NodeData newNode = new NodeData(neighbor.Key, f);
-          openList.Add(newNode);
+          openList.Add(newNode);  // wenn f bereits vorhanden -> kein add: openList.Contains(new NodeData(123, 0.2973786f))
           openListLookup.Add(newNode.Node, newNode);
         }
         closedList.Add(currentNode);
         closedListLookup.Add(currentNode);
+        i++;
       }
       throw new Exception(string.Format("No route found from {0} to {1}", sourceNodeId, targetNodeId));
Index: branches/RoutePlanning/HeuristicLab.Algorithms.GraphRouting/3.3/DijkstraAlgorithm.cs
===================================================================
--- branches/RoutePlanning/HeuristicLab.Algorithms.GraphRouting/3.3/DijkstraAlgorithm.cs	(revision 8640)
+++ branches/RoutePlanning/HeuristicLab.Algorithms.GraphRouting/3.3/DijkstraAlgorithm.cs	(revision 8640)
@@ -0,0 +1,114 @@
+﻿
+using System;
+using System.Collections.Generic;
+using HeuristicLab.Algorithms.GraphRouting.Interfaces;
+using HeuristicLab.Algorithms.GraphRouting.PriorityQueues;
+using HeuristicLab.Problems.RoutePlanning.Interfaces;
+namespace HeuristicLab.Algorithms.GraphRouting {
+  public class DijkstraAlgorithm : IRouter {
+    private IGraph graph;
+    private IHeap<float, long> unvisitedNodes;
+    private Dictionary<long, float> distances;
+    private Dictionary<long, long> predecessors;
+
+    public DijkstraAlgorithm(IGraph graph) {
+      this.graph = graph;
+    }
+
+    #region IRouter Members
+
+    public long[] Calculate(long sourceNodeId, long targetNodeId) {
+      unvisitedNodes = new BinaryHeap<float, long>(1000000);      // unvisited
+      //unvisitedNodes = new BinomialHeap<float, long>();    // unvisited
+      //unvisitedNodes = new FibonacciHeap<float, long>();   // unvisited
+      distances = new Dictionary<long, float>();
+      predecessors = new Dictionary<long, long>();
+
+      List<long> resultRoute = new List<long>();
+      if (sourceNodeId == targetNodeId) {
+        resultRoute.Add(sourceNodeId);
+        return resultRoute.ToArray();
+      }
+
+      long currentNode = sourceNodeId;
+      float currentWeight = 0;
+      unvisitedNodes.Insert(currentWeight, currentNode);
+
+      while (unvisitedNodes.Size > 0) {
+        KeyValuePair<float, long> data = unvisitedNodes.PeekMin();
+        unvisitedNodes.RemoveMin();
+        currentNode = data.Value;
+        currentWeight = data.Key;
+
+        //--------------
+        //Logger.LogToFile("cn = " + currentNode + " (" + currentWeight + ")");
+        //--------------
+
+        if (currentNode == targetNodeId) {
+          break;
+        }
+
+        distances[currentNode] = currentWeight;
+        RelaxNeighbors(currentNode, currentWeight);
+
+
+        //--------------
+        //Logger.LogToFile("");
+        //--------------
+      }
+
+      if (currentNode != targetNodeId) {
+        throw new Exception(string.Format("No route found from {0} to {1}", sourceNodeId, targetNodeId));
+      }
+      return GetRoute(targetNodeId).ToArray();
+    }
+
+    #endregion
+
+    public void RelaxNeighbors(long nodeId, float weight) {
+      Dictionary<long, float> currentNeighbors = graph.GetNeighborsWithWeight(nodeId);
+      foreach (KeyValuePair<long, float> neighbor in currentNeighbors) {
+        float totalWeight = weight + neighbor.Value;
+        if (totalWeight < GetDistance(neighbor.Key)) {
+
+          if (GetDistance(neighbor.Key) == float.MaxValue) {
+            unvisitedNodes.Insert(totalWeight, neighbor.Key);
+          } else {
+            unvisitedNodes.DecreaseKey(totalWeight, neighbor.Key);
+          }
+
+          distances[neighbor.Key] = totalWeight;
+          predecessors[neighbor.Key] = nodeId;
+
+          //--------------
+          //Logger.LogToFile("    neigb:" + neighbor.Key + " (" + totalWeight + ")");
+          //--------------
+        }
+      }
+    }
+
+    private float GetDistance(long id) {
+      float d;
+      if (distances.TryGetValue(id, out d)) {
+        return d;
+      } else { return float.MaxValue; }
+    }
+
+    private List<long> GetRoute(long nodeId) {
+      List<long> route = new List<long>();
+      long current = nodeId;
+      long next;
+
+      if (!predecessors.TryGetValue(current, out next)) {
+        return null;
+      }
+      route.Add(current);
+      while (predecessors.TryGetValue(current, out next)) {
+        current = predecessors[current];
+        route.Add(current);
+      }
+      route.Reverse();
+      return route;
+    }
+  }
+}
Index: branches/RoutePlanning/HeuristicLab.Algorithms.GraphRouting/3.3/DijkstraAlgorithmV2.cs
===================================================================
--- branches/RoutePlanning/HeuristicLab.Algorithms.GraphRouting/3.3/DijkstraAlgorithmV2.cs	(revision 8631)
+++ 	(revision )
@@ -1,136 +1,0 @@
-﻿
-using System;
-using System.Collections.Generic;
-using HeuristicLab.Algorithms.GraphRouting.Interfaces;
-using HeuristicLab.Problems.RoutePlanning.Interfaces;
-namespace HeuristicLab.Algorithms.GraphRouting {
-  public class DijkstraAlgorithmV2 : IRouter {
-    private IGraph graph;
-
-    private HashSet<long> visitedNodes;
-    private HashSet<long> unvisitedNodes;
-    private Dictionary<long, float> distances;
-    private Dictionary<long, long> predecessors;
-
-    public DijkstraAlgorithmV2(IGraph graph) {
-      this.graph = graph;
-    }
-
-    #region IRouter Members
-
-    public long[] Calculate(long sourceNodeId, long targetNodeId) {
-      visitedNodes = new HashSet<long>();        // visited
-      unvisitedNodes = new HashSet<long>();      // unvisited
-      distances = new Dictionary<long, float>();
-      predecessors = new Dictionary<long, long>();
-
-      List<long> resultRoute = new List<long>();
-      if (sourceNodeId == targetNodeId) {
-        resultRoute.Add(sourceNodeId);
-        return resultRoute.ToArray();
-      }
-
-      long currentNode = sourceNodeId;
-      distances.Add(currentNode, 0);
-      unvisitedNodes.Add(currentNode);
-
-      while (unvisitedNodes.Count > 0) {
-        currentNode = GetMinimumDistance(unvisitedNodes);
-        visitedNodes.Add(currentNode);
-        unvisitedNodes.Remove(currentNode);
-        if (currentNode == targetNodeId) {
-          break;
-        }
-        FindMinimalWeight(currentNode);
-      }
-
-      if (currentNode != targetNodeId) {
-        // target was not found
-        // maybe throw exception
-        throw new Exception(string.Format("No route found from {0} to {1}", sourceNodeId, targetNodeId));
-      }
-      return GetRoute(targetNodeId).ToArray();
-    }
-
-    #endregion
-
-    public long GetNodeIdWithRank(long sourceNodeId, int rank) {
-      visitedNodes = new HashSet<long>();        // visited
-      unvisitedNodes = new HashSet<long>();      // unvisited
-      distances = new Dictionary<long, float>();
-      predecessors = new Dictionary<long, long>();
-      int currentRank = 0;
-
-
-      long currentNode = sourceNodeId;
-      distances.Add(currentNode, 0);
-      unvisitedNodes.Add(currentNode);
-
-      while (unvisitedNodes.Count > 0) {
-        currentNode = GetMinimumDistance(unvisitedNodes);
-        visitedNodes.Add(currentNode);
-        unvisitedNodes.Remove(currentNode);
-        currentRank++;
-        if (currentRank == rank) {
-          break;
-        }
-        FindMinimalWeight(currentNode);
-      }
-      return currentNode;
-    }
-
-    private long GetMinimumDistance(HashSet<long> nodeIds) {
-      long minimum = -1;
-      foreach (long id in nodeIds) {
-        if (minimum == -1) minimum = id;
-        else {
-          if (GetDistance(id) < GetDistance(minimum)) {
-            minimum = id;
-          }
-        }
-      }
-      return minimum;
-    }
-
-    private float GetDistance(long id) {
-      float d;
-      if (distances.TryGetValue(id, out d)) {
-        return d;
-      } else { return float.MaxValue; }
-
-    }
-
-    private void FindMinimalWeight(long nodeId) {
-      //if (nodeId == 274265932) {
-      //  Console.WriteLine();
-      //}
-      Dictionary<long, float> currentNeighbors = graph.GetNeighborsWithWeight(nodeId);
-      foreach (KeyValuePair<long, float> neighbor in currentNeighbors) {
-        // update relax
-        float totalWeight = GetDistance(nodeId) + neighbor.Value;
-        if (GetDistance(neighbor.Key) > totalWeight) {
-          distances[neighbor.Key] = totalWeight;
-          predecessors[neighbor.Key] = nodeId;
-          unvisitedNodes.Add(neighbor.Key);
-        }
-      }
-    }
-
-    private List<long> GetRoute(long nodeId) {
-      List<long> route = new List<long>();
-      long current = nodeId;
-      long next;
-
-      if (!predecessors.TryGetValue(current, out next)) {
-        return null;
-      }
-      route.Add(current);
-      while (predecessors.TryGetValue(current, out next)) {
-        current = predecessors[current];
-        route.Add(current);
-      }
-      route.Reverse();
-      return route;
-    }
-  }
-}
Index: branches/RoutePlanning/HeuristicLab.Algorithms.GraphRouting/3.3/DijkstraNoDecAlgorithm.cs
===================================================================
--- branches/RoutePlanning/HeuristicLab.Algorithms.GraphRouting/3.3/DijkstraNoDecAlgorithm.cs	(revision 8631)
+++ branches/RoutePlanning/HeuristicLab.Algorithms.GraphRouting/3.3/DijkstraNoDecAlgorithm.cs	(revision 8640)
@@ -3,6 +3,6 @@
 using System.Collections.Generic;
 using HeuristicLab.Algorithms.GraphRouting.Interfaces;
+using HeuristicLab.Problems.RoutePlanning.Interfaces;
 using HeuristicLab.Algorithms.GraphRouting.PriorityQueues;
-using HeuristicLab.Problems.RoutePlanning.Interfaces;
 namespace HeuristicLab.Algorithms.GraphRouting {
   public class DijkstraNoDecAlgorithm : IRouter {
@@ -19,7 +19,11 @@
 
     public long[] Calculate(long sourceNodeId, long targetNodeId) {
-      unvisitedNodes = new BinHeap<float, long>(1000000);      // unvisited
+      unvisitedNodes = new NaivePriorityQueue<float, long>();
+      //unvisitedNodes = new BinaryHeap<float, long>(1000000);      // unvisited
       //unvisitedNodes = new BinomialHeap<float, long>();    // unvisited
-      //unvisitedNodes = new BinaryHeap<float, long>(float.MaxValue, float.MinValue, 1000000);   // unvisited
+      //unvisitedNodes = new BinaryHeapV2<float, long>(float.MaxValue, float.MinValue, 1000000);   // unvisited
+      //unvisitedNodes = new BinaryHeapV3<float, long>(float.MaxValue, float.MinValue, 1000000);   // unvisited
+      //unvisitedNodes = new Heap4<float, long>(float.MaxValue, float.MinValue, 1000000);   // unvisited
+      //unvisitedNodes = new FibonacciHeap<float, long>();   // unvisited
       distances = new Dictionary<long, float>();
       predecessors = new Dictionary<long, long>();
@@ -41,4 +45,8 @@
         currentWeight = data.Key;
 
+        //--------------
+        //Logger.LogToFile("cn = " + currentNode + " (" + currentWeight + ")");
+        //--------------
+
         if (currentNode == targetNodeId) {
           break;
@@ -49,4 +57,8 @@
           RelaxNeighbors(currentNode, currentWeight);
         }
+
+        //--------------
+        //Logger.LogToFile("");
+        //--------------
       }
 
@@ -67,4 +79,8 @@
           predecessors[neighbor.Key] = nodeId;
           unvisitedNodes.Insert(totalWeight, neighbor.Key);
+
+          //--------------
+          //Logger.LogToFile("    neigb:" + neighbor.Key + " (" + totalWeight + ")");
+          //--------------
         }
       }
Index: branches/RoutePlanning/HeuristicLab.Algorithms.GraphRouting/3.3/HeuristicLab.Algorithms.GraphRouting.csproj
===================================================================
--- branches/RoutePlanning/HeuristicLab.Algorithms.GraphRouting/3.3/HeuristicLab.Algorithms.GraphRouting.csproj	(revision 8631)
+++ branches/RoutePlanning/HeuristicLab.Algorithms.GraphRouting/3.3/HeuristicLab.Algorithms.GraphRouting.csproj	(revision 8640)
@@ -61,6 +61,7 @@
     <Compile Include="AStarAlgorithmV4.cs" />
     <Compile Include="AStarAlgorithmV5.cs" />
+    <Compile Include="DijkstraAlgorithm.cs" />
     <Compile Include="DijkstraNoDecAlgorithm.cs" />
-    <Compile Include="DijkstraAlgorithmV2.cs" />
+    <Compile Include="NaiveDijkstraAlgorithm.cs" />
     <Compile Include="GraphRoutingAlgorithm.cs" />
     <Compile Include="Interfaces\IHeap.cs" />
Index: branches/RoutePlanning/HeuristicLab.Algorithms.GraphRouting/3.3/NaiveDijkstraAlgorithm.cs
===================================================================
--- branches/RoutePlanning/HeuristicLab.Algorithms.GraphRouting/3.3/NaiveDijkstraAlgorithm.cs	(revision 8640)
+++ branches/RoutePlanning/HeuristicLab.Algorithms.GraphRouting/3.3/NaiveDijkstraAlgorithm.cs	(revision 8640)
@@ -0,0 +1,136 @@
+﻿
+using System;
+using System.Collections.Generic;
+using HeuristicLab.Algorithms.GraphRouting.Interfaces;
+using HeuristicLab.Problems.RoutePlanning.Interfaces;
+namespace HeuristicLab.Algorithms.GraphRouting {
+  // simple implemntation of disjkstra's algorithm
+  // based on: http://de.wikipedia.org/wiki/Dijkstra-Algorithmus
+  // (doesn't use heaps ... )
+  public class NaiveDijkstraAlgorithm : IRouter {
+    private IGraph graph;
+
+    private HashSet<long> visitedNodes;
+    private HashSet<long> unvisitedNodes;
+    private Dictionary<long, float> distances;
+    private Dictionary<long, long> predecessors;
+
+    public NaiveDijkstraAlgorithm(IGraph graph) {
+      this.graph = graph;
+    }
+
+    #region IRouter Members
+
+    public long[] Calculate(long sourceNodeId, long targetNodeId) {
+      visitedNodes = new HashSet<long>();        // visited
+      unvisitedNodes = new HashSet<long>();      // unvisited
+      distances = new Dictionary<long, float>();
+      predecessors = new Dictionary<long, long>();
+
+      List<long> resultRoute = new List<long>();
+      if (sourceNodeId == targetNodeId) {
+        resultRoute.Add(sourceNodeId);
+        return resultRoute.ToArray();
+      }
+
+      long currentNode = sourceNodeId;
+      distances.Add(currentNode, 0);
+      unvisitedNodes.Add(currentNode);
+
+      while (unvisitedNodes.Count > 0) {
+        currentNode = GetMinimumDistance(unvisitedNodes);
+        visitedNodes.Add(currentNode);
+        unvisitedNodes.Remove(currentNode);
+        if (currentNode == targetNodeId) {
+          break;
+        }
+        FindMinimalWeight(currentNode);
+      }
+
+      if (currentNode != targetNodeId) {
+        // target was not found
+        // maybe throw exception
+        throw new Exception(string.Format("No route found from {0} to {1}", sourceNodeId, targetNodeId));
+      }
+      return GetRoute(targetNodeId).ToArray();
+    }
+
+    #endregion
+
+    public long GetNodeIdWithRank(long sourceNodeId, int rank) {
+      visitedNodes = new HashSet<long>();        // visited
+      unvisitedNodes = new HashSet<long>();      // unvisited
+      distances = new Dictionary<long, float>();
+      predecessors = new Dictionary<long, long>();
+      int currentRank = 0;
+
+
+      long currentNode = sourceNodeId;
+      distances.Add(currentNode, 0);
+      unvisitedNodes.Add(currentNode);
+
+      while (unvisitedNodes.Count > 0) {
+        currentNode = GetMinimumDistance(unvisitedNodes);
+        visitedNodes.Add(currentNode);
+        unvisitedNodes.Remove(currentNode);
+        currentRank++;
+        if (currentRank == rank) {
+          break;
+        }
+        FindMinimalWeight(currentNode);
+      }
+      return currentNode;
+    }
+
+    private long GetMinimumDistance(HashSet<long> nodeIds) {
+      long minimum = -1;
+      foreach (long id in nodeIds) {
+        if (minimum == -1) minimum = id;
+        else {
+          if (GetDistance(id) < GetDistance(minimum)) {
+            minimum = id;
+          }
+        }
+      }
+      return minimum;
+    }
+
+    private float GetDistance(long id) {
+      float d;
+      if (distances.TryGetValue(id, out d)) {
+        return d;
+      } else { return float.MaxValue; }
+
+    }
+
+    private void FindMinimalWeight(long nodeId) {
+      Dictionary<long, float> currentNeighbors = graph.GetNeighborsWithWeight(nodeId);
+      foreach (KeyValuePair<long, float> neighbor in currentNeighbors) {
+        // update relax
+        float totalWeight = GetDistance(nodeId) + neighbor.Value;
+        if (GetDistance(neighbor.Key) > totalWeight) {
+          distances[neighbor.Key] = totalWeight;
+          predecessors[neighbor.Key] = nodeId;
+          unvisitedNodes.Add(neighbor.Key);
+        }
+      }
+    }
+
+    private List<long> GetRoute(long nodeId) {
+      List<long> route = new List<long>();
+      long current = nodeId;
+      long next;
+
+      if (!predecessors.TryGetValue(current, out next)) {
+        return null;
+      }
+      route.Add(current);
+      while (predecessors.TryGetValue(current, out next)) {
+        current = predecessors[current];
+        route.Add(current);
+      }
+      route.Reverse();
+      return route;
+    }
+  }
+}
Index: branches/RoutePlanning/HeuristicLab.Algorithms.GraphRouting/3.3/PriorityQueues/FibonacciHeap.cs
===================================================================
--- branches/RoutePlanning/HeuristicLab.Algorithms.GraphRouting/3.3/PriorityQueues/FibonacciHeap.cs	(revision 8631)
+++ branches/RoutePlanning/HeuristicLab.Algorithms.GraphRouting/3.3/PriorityQueues/FibonacciHeap.cs	(revision 8640)
@@ -47,8 +47,10 @@
         min = n;
       } else {
+        // concateneate the root list (becoming left sibling of root)
         n.Right = min;
         n.Left = min.Left;
         n.Right.Left = n;
         n.Left.Right = n;
+        // update point of minimum if necessary
         if (n.Key.CompareTo(min.Key) < 0) {
           min = n;
@@ -103,7 +105,9 @@
 
     private void Link(HeapNode y, HeapNode z) {
+      // remove y from the root list
       y.Left.Right = y.Right;
       y.Right.Left = y.Left;
 
+      // make y a child of x, ...
       y.Parent = z;
       if (z.Child == null) {
@@ -117,4 +121,6 @@
         y.Right.Left = y;
       }
+
+      // ... incrementing degree[x]
       z.Degree++;
       y.Mark = false;
@@ -122,9 +128,10 @@
 
     private void Consolidate() {
-      //TODO: explain magic number
-      HeapNode[] A = new HeapNode[45];
+      int dn = (int)Math.Floor(Math.Log(size) / Math.Log(2)) + 1; // log2size[Heap]
+      HeapNode[] A = new HeapNode[dn];  // consolidation array
       HeapNode start = min;
       HeapNode w = min;
 
+      // for each node w in the root list
       do {
         HeapNode x = w;
@@ -157,5 +164,6 @@
       min = null;
 
-      for (int i = 0; i < 45; i++) {
+      // find the new minimum key
+      for (int i = 0; i < dn; i++) {
         if (A[i] != null) {
           HeapNode n = A[i];
