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!
Advertisements
[…] 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. […]
LikeLike
[…] For the missing parts check my previous blog posts. A Star Algorithm Java Implementation Dijskstra’s Algorithm Java Implementation […]
LikeLiked by 1 person