Utilizing Comparator while implementing Dijkstra and A* path search algorithms in Java

Both Dijkstra and A* algorithms are well known and understood and I will skip the part explaining them. I would recommend going through the already available literature on these topics if you need a refresher.

The main difference between the two algorithms stems from the way they go on about selecting the next node to explore in a graph.

Dijkstra greedily explores the next closest neighbour from the current node and while this approach is understandable, it is not what I call "focused".

It spirals out starting from the source and keeps on searching outwards in all directions.
So, For E.g if you were to start in San Fransisco and search for Portland, Oregon on a map (represented, ofcourse, as a graph) , it would have in the same time searched some places in Mexico too !!

A* adds Heuristics to the mix. This heuristic function add some intelligence to the way for finding the next node. You could theoretically add a lot of interesting heuristics to this but one of the most basic ones is the distance to your target node.

The idea is to see that with each iteration you should be getting closer to your target node and therefore, select nodes that have the lowest (D(C) + D(T)), where D(C) would be the distance from the current node (essentially giving you your closest neighbour) and D(T) would be the distance to the taget location (straight-line distance, heuristic function has to be smaller for the search to work).

This is how then, we could implement these two algorithms:

public List<GeographicPoint> dijkstra(GeographicPoint start,
 GeographicPoint goal, Consumer<GeographicPoint> nodeSearched)
{

Comparator<GraphVertice> distanceFunction = new DistanceComparator();
return shortestPath(start,goal,nodeSearched,distanceFunction);

}

public List<GeographicPoint> aStarSearch(GeographicPoint start,
GeographicPoint goal, Consumer<GeographicPoint> nodeSearched)
{

Comparator<GraphVertice> function = new HeuristicComparator();
return shortestPath(start,goal,nodeSearched,function);


} 

and then in your shortestPath function , create the PriorityQueue like this:

PriorityQueue<GraphVertice> pq = new PriorityQueue<GraphVertice>(function);

This Comparator object we supply would be used while adding nodes into the priority queue that is generally maintained while visiting nodes.
The DistanceComparator compares two graph Nodes by the distance to the current node in context, while the heuristic one would take into account both this distance as well as the straight-line distance to target.

The result between these two algorithms can be seen from the screenshot below.

We are searching for the shortest distance between two intersections in New York's busy Manhattan area and:

a.) You can see how Dijsktra creates a spiral from the start to the end location ( The green flag is the end).

b.) The A* algorithm quickly moves towards the nodes because it is geared to favor nodes closer to the destination.

A short note here: If we only used heuristic ( D(T) ), instead of the sum, we would no longer guarantee that the path is optimal. It would, in most real world cases, find a path faster but sub-optimally.

Also, the the HeuristicComparator is not named very appropriately , as it utilizes the sum of both the functions.