Index: branches/RoutePlanning/HeuristicLab.Algorithms.GraphRouting/3.3/DijkstraNoDecAlgorithm.cs
===================================================================
--- branches/RoutePlanning/HeuristicLab.Algorithms.GraphRouting/3.3/DijkstraNoDecAlgorithm.cs	(revision 8539)
+++ branches/RoutePlanning/HeuristicLab.Algorithms.GraphRouting/3.3/DijkstraNoDecAlgorithm.cs	(revision 8539)
@@ -0,0 +1,97 @@
+﻿
+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 DijkstraNoDecAlgorithm : IRouter {
+    private IGraph graph;
+    private IHeap<float, long> unvisitedNodes;
+    private Dictionary<long, float> distances;
+    private Dictionary<long, long> predecessors;
+
+    public DijkstraNoDecAlgorithm(IGraph graph) {
+      this.graph = graph;
+    }
+
+    #region IRouter Members
+
+    public long[] Calculate(long sourceNodeId, long targetNodeId) {
+      unvisitedNodes = new BinHeap<float, long>(1000000);      // unvisited
+      //unvisitedNodes = new BinomialHeap<float, long>();    // unvisited
+      //unvisitedNodes = new BinaryHeap<float, long>(float.MaxValue, float.MinValue, 1000000);   // 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;
+
+        if (currentNode == targetNodeId) {
+          break;
+        }
+
+        if (currentWeight <= GetDistance(currentNode)) {
+          distances[currentNode] = currentWeight;
+          RelaxNeighbors(currentNode, currentWeight);
+        }
+      }
+
+      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)) {
+          distances[neighbor.Key] = totalWeight;
+          predecessors[neighbor.Key] = nodeId;
+          unvisitedNodes.Insert(totalWeight, neighbor.Key);
+        }
+      }
+    }
+
+    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/HeuristicLab.Algorithms.GraphRouting.csproj
===================================================================
--- branches/RoutePlanning/HeuristicLab.Algorithms.GraphRouting/3.3/HeuristicLab.Algorithms.GraphRouting.csproj	(revision 8527)
+++ branches/RoutePlanning/HeuristicLab.Algorithms.GraphRouting/3.3/HeuristicLab.Algorithms.GraphRouting.csproj	(revision 8539)
@@ -61,4 +61,5 @@
     <Compile Include="AStarAlgorithmV4.cs" />
     <Compile Include="AStarAlgorithmV5.cs" />
+    <Compile Include="DijkstraNoDecAlgorithm.cs" />
     <Compile Include="DijkstraAlgorithmV2.cs" />
     <Compile Include="GraphRoutingAlgorithm.cs" />
Index: branches/RoutePlanning/HeuristicLab.Algorithms.GraphRouting/3.3/PriorityQueues/BinHeap.cs
===================================================================
--- branches/RoutePlanning/HeuristicLab.Algorithms.GraphRouting/3.3/PriorityQueues/BinHeap.cs	(revision 8527)
+++ branches/RoutePlanning/HeuristicLab.Algorithms.GraphRouting/3.3/PriorityQueues/BinHeap.cs	(revision 8539)
@@ -92,5 +92,5 @@
       while ((left < size - 1 && data[idx].Key.CompareTo(data[left].Key) != -1) ||
              (right < size - 1 && data[idx].Key.CompareTo(data[right].Key) != -1)) {
-        if ((right >= size - 1) || (data[idx].Key.CompareTo(data[right].Key) == -1)) {
+        if ((right >= size - 1) || (data[left].Key.CompareTo(data[right].Key) == -1)) {
           Swap(left, idx);
           idx = left;
Index: branches/RoutePlanning/HeuristicLab.Algorithms.GraphRouting/3.3/PriorityQueues/BinaryHeap.cs
===================================================================
--- branches/RoutePlanning/HeuristicLab.Algorithms.GraphRouting/3.3/PriorityQueues/BinaryHeap.cs	(revision 8527)
+++ branches/RoutePlanning/HeuristicLab.Algorithms.GraphRouting/3.3/PriorityQueues/BinaryHeap.cs	(revision 8539)
@@ -1,8 +1,10 @@
 ﻿
 using System;
+using System.Collections.Generic;
+using HeuristicLab.Algorithms.GraphRouting.Interfaces;
 namespace HeuristicLab.Algorithms.GraphRouting.PriorityQueues {
   // implementation based on C++ version from Peter Sanders
   // http://www.mpi-inf.mpg.de/~sanders/programs/spq/
-  public sealed class BinaryHeap<K, V> where K : IComparable {
+  public sealed class BinaryHeap<K, V> : IHeap<K, V> where K : IComparable {
     private class KNElement {
       public K Key { get; set; }
@@ -31,4 +33,11 @@
     public int Size {
       get { return size; }
+    }
+
+    public KeyValuePair<K, V> PeekMin() {
+      if (size == 0) {
+        throw new InvalidOperationException("Heap is empty");
+      }
+      return new KeyValuePair<K, V>(data[1].Key, data[1].Value);
     }
 
