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!

  1. […] 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. […]

    Like

    Reply

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

    Liked by 1 person

    Reply

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: