# Python 95% A* algorithm with explanation

• There are some posts using BFS + PriorityQueue implementations in this question, some of them actually use A* algorithm but without any explanation. It is kind of dangerous since A* is not applicable for all shortest path problems.

``````    def heuristic(a, b): # it is an admissible heuristic
return abs(b[0] - a[0]) + abs(b[1] - a[1])
``````

A* algorithm can be used to solve the problem because the distance heuristic function of the goal and current location is admissible, that means this heuristic never overestimates the real distance between the goal and current location.

Basically A* algorithm is a best-first search algorithm. It stores the neighbors in a priorityQueue and explores the most promising neighbor first. An admissible heuristic will guarantee the shortest path on the first time you reach the goal because the later visited positions will have worse results than their heuristic values.

For more details about A* algorithm, please refer the wiki page: https://en.wikipedia.org/wiki/A*_search_algorithm

Python implementation:

``````from heapq import *

class Solution(object):
def shortestDistance(self, maze, start, destination):
"""
:type maze: List[List[int]]
:type start: List[int]
:type destination: List[int]
:rtype: int
"""

def get_neighbors(start):
neighbors = []
i, j = start
if i - 1 >= 0 and maze[i-1][j] == 0:
while i - 1 >= 0 and maze[i-1][j] == 0: i-=1
neighbors.append((i,j))
i, j = start
if j - 1 >= 0 and maze[i][j-1] == 0:
while j - 1 >= 0 and maze[i][j-1] == 0: j -= 1
neighbors.append((i, j))
i, j = start
if i + 1 < len(maze) and maze[i+1][j] == 0:
while i + 1 < len(maze) and maze[i+1][j] == 0: i += 1
neighbors.append((i, j))
i, j = start
if j + 1 < len(maze[0]) and maze[i][j+1] == 0:
while j + 1 < len(maze[0]) and maze[i][j+1] == 0: j += 1
neighbors.append((i, j))
return neighbors

def heuristic(a, b):
return abs(b[0] - a[0]) + abs(b[1] - a[1])

start = (start[0], start[1])
destination = (destination[0], destination[1])
gscore = {start: 0}
fscore = {start: heuristic(start, destination)}
open_heap = []
open_set = set()
close_set = set()

heappush(open_heap, (fscore[start], start))

while open_heap:

current = heappop(open_heap)[1]
open_set.remove(current)

if current == destination:
return gscore[current]

for neighbor in get_neighbors(current):
tentative_score = gscore[current] + heuristic(current, neighbor)
if neighbor in close_set and tentative_score >= gscore.get(neighbor, 0):
continue

if tentative_score < gscore.get(neighbor, 0) or neighbor not in open_set:
gscore[neighbor] = tentative_score
fscore[neighbor] = tentative_score + heuristic(neighbor, destination)
if neighbor in open_set:
for i in xrange(len(open_heap)):
if open_heap[i][1] == neighbor:
open_heap.pop(i)
break
heappush(open_heap, (fscore[neighbor], neighbor))