Dijkstra’s Algorithm implementation in Java

The Breadth First Search (BFS) algorithm basically checks only if there is a path from node A to node B. It’ doesn’t necessarily find the shortest path between two graph nodes. Here comes Dijkstra into the game. Dijkstra’s algorithm finds the shortest possible route between two graph nodes. The main difference between Dijkstra and BFS is the Priority Queue that Dijkstra uses. It basically prioritizes the shorter possible route to the end node. For explanation how Dijkstra exactly works, check this video. If you want to compare BFS with Dijkstra check this java implementation.

‘Nuff said! Here’s the source.

/** Find the path from start to goal using Dijkstra's algorithm
	 *
	 * @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> dijkstra(GeographicPoint start,
										  GeographicPoint goal, Consumer<GeographicPoint> nodeSearched)
	{

		MapNode startNode = pointNodeMap.get(start);
		MapNode endNode = pointNodeMap.get(goal);

		HashMap<MapNode,MapNode> parentMap = new HashMap<MapNode,MapNode>();
		HashSet<MapNode> visited = new HashSet<MapNode>();
		Map<MapNode, Double> distances = initializeAllToInfinity();
		Queue<MapNode> priorityQueue = initQueue();

		// enque Start node 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) ){	

						// 1. calculate distance to neighbor. 2. calculate dist from start node
						double neighborDistance = current.calculateDistance(neighbor);
						double totalDistance = current.getDistanceToStart() + neighborDistance;

						// check if distance smaller
						if(totalDistance < distances.get(neighbor)){
							// update n's distance
							distances.put(neighbor, totalDistance);
							// used for PQ
							neighbor.setDistanceToStart(totalDistance);
							// set parent
							parentMap.put(neighbor, current);
							// enqueue
							priorityQueue.add(neighbor);
						}
					}
				}
			}
		}
		return null;
	}

Priority queue can be initialized like this.

/**
	 * @return Priority Queue
	 */
	private PriorityQueue<MapNode> initQueue() {
		return new PriorityQueue<>(10, new Comparator<MapNode>() {
			public int compare(MapNode x, MapNode y) {
				if (x.getDistanceToStart() < y.getDistanceToStart()) 		        { 		            return -1; 		        } 		        if (x.getDistanceToStart() > y.getDistanceToStart())
		        {
		            return 1;
		        }
		        return 0;
			};
		});
	}

And a structure to hold current node distances from the start node.

private Map<MapNode, Double> initializeAllToInfinity() {
		Map<MapNode,Double> distances = new HashMap<>();

		Iterator<MapNode> iter = pointNodeMap.values().iterator();
		while (iter.hasNext()) {
			MapNode node = iter.next();
			distances.put(node, Double.POSITIVE_INFINITY);
		}
		return distances;
	}

 

Enjoy it… Cheers!