Index: branches/RoutePlanning/HeuristicLab.Algorithms.GraphRouting/3.3/AStarAlgorithm.cs
===================================================================
--- branches/RoutePlanning/HeuristicLab.Algorithms.GraphRouting/3.3/AStarAlgorithm.cs	(revision 8321)
+++ branches/RoutePlanning/HeuristicLab.Algorithms.GraphRouting/3.3/AStarAlgorithm.cs	(revision 8321)
@@ -0,0 +1,87 @@
+﻿
+using System;
+using System.Collections.Generic;
+using HeuristicLab.Problems.RoutePlanning.Graph;
+namespace HeuristicLab.Algorithms.GraphRouting {
+  class AStarAlgorithm : IRouter {
+    private Graph graph;
+
+    private Dictionary<long, float> distances;
+    private Dictionary<long, long> predecessors;
+    private List<float> closedList = new List<float>();
+    private PriorityQueue<float, long> openList;
+
+    public AStarAlgorithm(Graph graph) {
+      this.graph = graph;
+    }
+
+    #region IRouter Members
+
+    public long[] Calculate(long sourceNodeId, long targetNodeId) {
+      distances = new Dictionary<long, float>();
+      predecessors = new Dictionary<long, long>();
+      closedList = new List<float>();
+      openList = new PriorityQueue<float, long>();
+
+      long currentNode = sourceNodeId;
+
+      openList.Enqueue(currentNode, 0);
+      distances.Add(currentNode, 0);
+
+      while (openList.Count > 0) {
+        currentNode = openList.Dequeue();
+        if (currentNode == targetNodeId) {
+          return ReconstructPath(currentNode).ToArray();
+        }
+
+        Dictionary<long, float> currentNeighbors = graph.GetNeighbors(currentNode);
+        foreach (KeyValuePair<long, float> neighbor in currentNeighbors) {
+          if (closedList.Contains(neighbor.Key))
+            continue;
+
+          float costsFromStart = GetDistance(currentNode) + neighbor.Value;
+
+          if (openList.Contains(neighbor.Key) && costsFromStart > GetDistance(neighbor.Key))
+            continue;
+
+          distances[neighbor.Key] = costsFromStart;
+          predecessors[neighbor.Key] = currentNode;
+
+          float f = costsFromStart + graph.EstimatedCosts(neighbor.Key, targetNodeId);
+          if (openList.Contains(neighbor.Key)) {
+            openList.Remove(neighbor.Key);
+          }
+          openList.Enqueue(neighbor.Key, f);
+        }
+      }
+      throw new Exception(string.Format("No route found from {0} to {1}", sourceNodeId, targetNodeId));
+    }
+
+    #endregion
+
+    private float GetDistance(long id) {
+      float d;
+      if (distances.TryGetValue(id, out d)) {
+        return d;
+      } else { return float.MaxValue; }
+
+    }
+
+    private List<long> ReconstructPath(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 8316)
+++ branches/RoutePlanning/HeuristicLab.Algorithms.GraphRouting/3.3/HeuristicLab.Algorithms.GraphRouting.csproj	(revision 8321)
@@ -57,8 +57,11 @@
   </ItemGroup>
   <ItemGroup>
+    <Compile Include="AStarAlgorithm.cs" />
     <Compile Include="DijkstraAlgorithm.cs" />
     <Compile Include="GraphRoutingAlgorithm.cs" />
     <Compile Include="IRouter.cs" />
+    <Compile Include="Pair.cs" />
     <Compile Include="Plugin.cs" />
+    <Compile Include="PriorityQueue.cs" />
     <Compile Include="Properties\AssemblyInfo.cs" />
   </ItemGroup>
Index: branches/RoutePlanning/HeuristicLab.Algorithms.GraphRouting/3.3/Pair.cs
===================================================================
--- branches/RoutePlanning/HeuristicLab.Algorithms.GraphRouting/3.3/Pair.cs	(revision 8321)
+++ branches/RoutePlanning/HeuristicLab.Algorithms.GraphRouting/3.3/Pair.cs	(revision 8321)
@@ -0,0 +1,38 @@
+﻿
+using System;
+using System.Collections.Generic;
+namespace HeuristicLab.Algorithms.GraphRouting {
+  public class Pair<T> {
+    public T First { get; private set; }
+    public T Second { get; private set; }
+
+    public Pair(T first, T second) {
+      First = first;
+      Second = second;
+    }
+
+    public override int GetHashCode() {
+      return First.GetHashCode() ^ Second.GetHashCode();
+    }
+
+    public override bool Equals(object other) {
+      Pair<T> pair = other as Pair<T>;
+      if (pair == null) {
+        return false;
+      }
+      return (this.First.Equals(pair.First) && this.Second.Equals(pair.Second));
+    }
+  }
+
+  class PairComparer<T> : IComparer<Pair<T>> where T : IComparable {
+    public int Compare(Pair<T> x, Pair<T> y) {
+      if (x.First.CompareTo(y.First) < 0) {
+        return -1;
+      } else if (x.First.CompareTo(y.First) > 0) {
+        return 1;
+      } else {
+        return x.Second.CompareTo(y.Second);
+      }
+    }
+  }
+}
Index: branches/RoutePlanning/HeuristicLab.Algorithms.GraphRouting/3.3/PriorityQueue.cs
===================================================================
--- branches/RoutePlanning/HeuristicLab.Algorithms.GraphRouting/3.3/PriorityQueue.cs	(revision 8321)
+++ branches/RoutePlanning/HeuristicLab.Algorithms.GraphRouting/3.3/PriorityQueue.cs	(revision 8321)
@@ -0,0 +1,48 @@
+﻿
+using System;
+using System.Collections.Generic;
+namespace HeuristicLab.Algorithms.GraphRouting {
+  public class PriorityQueue<P, T> where P : IComparable {
+    SortedList<Pair<P>, T> list;
+    P dummy;
+
+    public PriorityQueue() {
+      list = new SortedList<Pair<P>, T>(new PairComparer<P>());
+    }
+
+    public int Count {
+      get { return list.Count; }
+    }
+
+    public void Enqueue(T item, P priority) {
+      list.Add(new Pair<P>(priority, dummy), item);
+      //count++;
+    }
+
+    public T Dequeue() {
+      T item = list[list.Keys[0]];
+      list.RemoveAt(0);
+      return item;
+    }
+
+    public bool Contains(T item) {
+      return list.ContainsValue(item);
+    }
+
+    public bool Remove(T item) {
+      bool delete = false;
+      KeyValuePair<Pair<P>, T> toDelete = new KeyValuePair<Pair<P>, T>();
+      foreach (var pair in list) {
+        if (pair.Value.Equals(item)) {
+          delete = true;
+          toDelete = pair;
+        }
+      }
+      if (delete) {
+        return list.Remove(toDelete.Key);
+      }
+      return false;
+    }
+
+  }
+}
Index: branches/RoutePlanning/HeuristicLab.Problems.RoutePlanning/3.3/Graph/Graph.cs
===================================================================
--- branches/RoutePlanning/HeuristicLab.Problems.RoutePlanning/3.3/Graph/Graph.cs	(revision 8316)
+++ branches/RoutePlanning/HeuristicLab.Problems.RoutePlanning/3.3/Graph/Graph.cs	(revision 8321)
@@ -117,4 +117,17 @@
       return (float)weight;
     }
+
+    public float EstimatedCosts(long sourceId, long targetId) {
+      Vertex<Node> source = GetVertex(sourceId);
+      Vertex<Node> target = GetVertex(targetId);
+      return EstimatedCosts(source, target);
+    }
+
+    public float EstimatedCosts(Vertex<Node> source, Vertex<Node> target) {
+      double distance = Utils.Distance(source.Node.Point, target.Node.Point);
+      int speed = 130;
+      double costs = (distance / speed) * 3.6;
+      return (float)costs;
+    }
   }
 }
Index: branches/RoutePlanning/HeuristicLab.Problems.RoutePlanning/3.3/Graph/Route.cs
===================================================================
--- branches/RoutePlanning/HeuristicLab.Problems.RoutePlanning/3.3/Graph/Route.cs	(revision 8321)
+++ branches/RoutePlanning/HeuristicLab.Problems.RoutePlanning/3.3/Graph/Route.cs	(revision 8321)
@@ -0,0 +1,33 @@
+﻿
+namespace HeuristicLab.Problems.RoutePlanning.Graph {
+  // represent linked vertices
+  public class Route {
+    private long headVertexId;
+    public long HeadVertexId {
+      get { return headVertexId; }
+    }
+
+    private float weight;
+    public float Weight {
+      get { return weight; }
+    }
+
+    private Route tail;
+    public Route Tail {
+      get { return tail; }
+    }
+
+    public Route(long vertexId) {
+      this.headVertexId = vertexId;
+      this.weight = 0;
+      this.tail = null;
+    }
+
+    public Route(long vertexId, float weight, Route tail) {
+      this.headVertexId = vertexId;
+      this.weight = weight;
+      this.tail = tail;
+    }
+
+  }
+}
