A* algorithm can be seen as an heuristic extension of Dijkstra’s. Whereas in the Dijkstra’s priority-queue ordering is based only on the distance from the start node to the current, A* algorithm additionally calculates the distance from the current node to the goal-node. Thus the ordering in the priority queue is different and the algorithm calculates more “straightforward” towards the end node in a graph and hence is significantly faster in finding the path than the Dijkstra. For detailed explanation how A* works check this link out. You can also find Dijkstra’s java implementation here.

‘Nuff said. Here’s the source…

/** Find the path from start to goal using A-Star search * * @param start The starting location * @param goal The goal location * @return The list of intersections that form the shortest path from * start to goal (including both start and goal). */ public List<GeographicPoint> aStarSearch(GeographicPoint start, GeographicPoint goal) { MapNode startNode = pointNodeMap.get(start); MapNode endNode = pointNodeMap.get(goal); // setup for A* HashMap<MapNode,MapNode> parentMap = new HashMap<MapNode,MapNode>(); HashSet<MapNode> visited = new HashSet<MapNode>(); Map<MapNode, Double> distances = initializeAllToInfinity(); Queue<MapNode> priorityQueue = initQueue(); // enque StartNode, with distance 0 startNode.setDistanceToStart(new Double(0)); distances.put(startNode, new Double(0)); priorityQueue.add(startNode); MapNode current = null; while (!priorityQueue.isEmpty()) { current = priorityQueue.remove(); if (!visited.contains(current) ){ visited.add(current); // if last element in PQ reached if (current.equals(endNode)) return reconstructPath(parentMap, startNode, endNode, 0); Set<MapNode> neighbors = getNeighbors(current); for (MapNode neighbor : neighbors) { if (!visited.contains(neighbor) ){ // calculate predicted distance to the end node double predictedDistance = neighbor.getLocation().distance(endNode.getLocation()); // 1. calculate distance to neighbor. 2. calculate dist from start node double neighborDistance = current.calculateDistance(neighbor); double totalDistance = current.getDistanceToStart() + neighborDistance + predictedDistance; // check if distance smaller if(totalDistance < distances.get(neighbor) ){ // update n's distance distances.put(neighbor, totalDistance); // used for PriorityQueue neighbor.setDistanceToStart(totalDistance); neighbor.setPredictedDistance(predictedDistance); // set parent parentMap.put(neighbor, current); // enqueue priorityQueue.add(neighbor); } } } } } return null; }

Basically, the only difference to Dijkstra’s algorithm are the following few lines, where distance to the end node is added to the total distance:

// calculate predicted distance to the end node double predictedDistance = neighbor.getLocation().distance(endNode.getLocation()); // 1. calculate distance to neighbor. 2. calculate total distance from start and to the end node double neighborDistance = current.calculateDistance(neighbor); double totalDistance = current.getDistanceToStart() + neighborDistance + predictedDistance;

Additional methods for path reconstruction and priority-queue initialization can be found here.

Enjoy the source and have fun.

[…] the missing parts check my previous blog posts. A Star Algorithm Java Implementation Dijskstra’s Algorithm Java […]

LikeLiked by 1 person