A* Algorithm

Applies to problems when we are given a start point and an end point coordinates(2D array). There can be some nodes which are blocked or are obstacle and can’t move pass through. And need to find the minimum distance between start and end point, providing we can move in 4 direction (up, down, left, right).

Manhattan Distance between two nodes is the L shaped path distance between two nodes. (In case when we can move only in 4 directions). 
In case of diagonal consideration, use Euclidean distance which is diagonal distance from two nodes.

Suppose, start point is A (0, 1) and end point B (4,3)

Manhattan Distance = A(0,1) — B(4,3) = (4–0) + (3–1) = 4 + 2 = 6 units of minimum distance from A to B (Heuristic distance)

For solving this problem we need to calculate the value of three variables for every node we move:

G = distance from start node to current node
H = heuristic distance from current node to end node or Manhattan Distance
F = G + H

To check which node to move next, need to check the minimum F value between open nodes that are not visited.

In Case when nodes have F score is same, check for lowest G score, and pick that node.

In case when F, G are same, choose randomly any node and proceed with above rule for unvisited node.

Once visit a node, mark that as visited and for fetching the path update each node while visiting that from where it come from. (>, < can use arrows).

A* vs Dijkstra Algorithm?
A* algorithm reach the end nodes with a heuristic distance(guess distance) and eliminating the nodes having higher heuristic distance and making it much faster from Dijkstra as Dijkstra works like a flower path which will consider every node and every possible path from that node to end node and find the minimum distance path.

So, for implementation we need to have a node with lowest F values. In case we add all nodes in array and for finding the node with lowest F value our complexity could become O(n) where n = w * h, where w is width and h is height of 2D array of nodes.

The proper data structure would be priority queue, as it handle the minimum value node in better complexity with O(log(n)).

Always start with a start node , G= 0 in start node.

Pseudo code

min heap = new min heap ([start])
while min heap is not empty: 
  # remove the lowest F value node from min heap
  node = min heap.pop()
  if node == end: 
    break
  # if the node is not empty then check for all neighbour nodes
  for neighbour in node.neighbours: 
   if obstacle: 
      continue 
   update F, G, H score
   # then add the node in the min heap with updated F score, if the               #neighbour is already in the min heap then just update its F score
  #  insert, update min heap 
# end of loop, if any node doesn’t match with end node then there is no path to reach end node and if it matches with end node then we get the desired minimum distance between two nodes

Code

Time complexity = O( w*h * log(w*h)) = O(n*log(n))
Auxiliary space we are using is min heap : Space complexity = O(w*h) = O(n)