A Star (A*) Algorithm Implementation in Java

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.