1091. Shortest Path in Binary Matrix (A Star)¶
Edited by Charles
Medium · Python · Graph
Problem
Read the original problem on LeetCode.
The official page contains the problem statement, examples, and constraints.
Explanation, examples & other approaches
Core idea
See the Python implementation and detailed notes below.
Original study notes follow, including intermediate snippets and earlier attempts.
Approach: A* Search¶
Core Idea¶
We need to find the shortest clear path from:
to:
A cell with value 0 can be visited, while a cell with value 1 is blocked.
From each cell, we can move in 8 directions:
Since every move has the same cost, BFS can solve this problem.
However, we can also use A* to guide the search toward the destination and potentially explore fewer unnecessary cells.
A* Search¶
A* uses three important values:
g(n) = actual cost from the start to the current node
h(n) = estimated cost from the current node to the goal
f(n) = g(n) + h(n)
For this problem:
We can visualize them as:
Meaning of Each Value¶
g(n) is the actual path length we have already traveled.
h(n) estimates how far the current cell is from the destination.
f(n) estimates the total length of a path that goes through the current cell.
A* uses:
as the priority in the min-heap.
Therefore, A* prefers nodes that have:
Why Use Chebyshev Distance?¶
The problem allows movement in 8 directions.
For a current cell:
and the goal:
the row difference is:
and the column difference is:
Since diagonal movement is allowed, one move can reduce both the row difference and the column difference at the same time.
Therefore, if there were no obstacles, the minimum number of moves required is:
This is the Chebyshev Distance.
We implement it as:
For example:
We can move diagonally twice:
and then vertically twice:
Total:
which is:
Therefore:
is a natural heuristic for this problem.
Why Is Chebyshev Distance a Valid Heuristic?¶
The heuristic should not overestimate the actual remaining shortest-path cost.
Chebyshev Distance calculates the shortest possible distance when we ignore all obstacles.
Without obstacles:
Adding obstacles can only make the actual path equal or longer:
Therefore, the heuristic does not overestimate the actual cost.
This makes it suitable for A*.
Why Not Use Manhattan Distance?¶
Manhattan Distance is:
It is natural when movement is only allowed in 4 directions:
But this problem allows diagonal movement.
For example:
The actual minimum number of moves is:
But Manhattan Distance gives:
which overestimates the true minimum cost.
Therefore:
Initial Check¶
If either the start or the destination is blocked:
there cannot be a valid path.
Therefore, we immediately return:
Eight Possible Moves¶
We define all 8 directions:
For the current node:
the next node is:
Define minDist¶
We use:
where:
represents:
The minimum actual path length
gfound so far from(0, 0)to(r, c).
It stores g, not f.
This distinction is very important.
Why Does the Starting Distance Equal 1?¶
We initialize:
because the problem defines path length as the number of cells in the path, not the number of edges.
For example:
contains:
so the path length is:
Therefore, at the starting cell:
rather than 0.
Initialize the Min-Heap¶
The heap stores:
In the code:
At the starting node:
Therefore:
Pop the Most Promising Node¶
We pop:
In this code:
The variable name curDist here represents the A* priority f.
The actual path length is:
This distinction is important.
Skip Stale States¶
A node may be pushed into the heap multiple times.
For example, suppose we first find:
and push it into the heap.
Later, we find a better path:
and push it again.
The heap now contains both states:
But:
When the old state with g = 8 is eventually popped, we skip it:
Notice that we compare:
not:
because minDist stores actual distances g.
Why Return steps?¶
When we reach:
we return:
because steps is:
which is the actual shortest path length from the start to the goal.
Remember:
The problem asks for the actual shortest path length, so conceptually the answer is g.
At the goal:
so:
Thus f and g happen to have the same value at the goal, but returning g is conceptually clearer.
Relaxation¶
For every valid neighbor:
This calculates the new actual distance:
because moving to a neighboring cell costs one additional step.
If:
we have found a better path to nextNode.
Therefore:
Calculate the New A* Priority¶
After obtaining the new actual distance:
we calculate:
which means:
where:
newG = actual distance from start to nextNode
newH = estimated distance from nextNode to goal
newF = estimated total path cost
Then:
Again, the heap stores:
The Most Important Part of A*¶
The core process can be summarized as:
Current Node
|
| actual movement cost = 1
↓
Next Node
|
├── newG = currentG + 1
|
├── newH = heuristic(nextNode)
|
└── newF = newG + newH
|
↓
Push to Heap
In code:
newSteps = steps + 1
if newSteps < minDist[nextNode[0]][nextNode[1]]:
minDist[nextNode[0]][nextNode[1]] = newSteps
newLen = newSteps + self.dist(nextNode)
heapq.heappush(
minHeap,
(newLen, newSteps, nextNode)
)
A* vs Dijkstra¶
Dijkstra uses:
It only considers the actual distance traveled so far.
A* uses:
It considers both:
Therefore:
Dijkstra:
Start → expands outward based on g
A*:
Start → searches more toward the Goal
based on g + h
The heuristic gives A* a sense of direction.
A* vs Greedy Best-First Search¶
There are three related strategies:
| Algorithm | Priority |
|---|---|
| Dijkstra | g |
| Greedy Best-First Search | h |
| A* | g + h |
Dijkstra¶
Only considers how much cost has already been paid.
Greedy Best-First Search¶
Only considers how close a node appears to be to the destination.
This may aggressively move toward the goal but can choose a bad route because it ignores the cost already paid.
A*¶
Balances both:
This is why A* can be both goal-directed and still find the shortest path when using an appropriate heuristic.
Complexity¶
There are at most:
cells.
Each cell has at most:
neighbors.
Heap operations take:
Therefore, a standard upper-bound analysis is:
The distance matrix and heap may contain up to O(n²) states:
Remember the three values in A*¶
In this implementation:
The heap is ordered by f¶
A* uses f to decide which node should be explored first.
Relaxation must use g¶
When moving to a neighbor:
which means:
Do not use:
because f already contains the heuristic.
minDist stores g, not f¶
Therefore, the stale-state check is:
For 8-direction movement, use Chebyshev Distance¶
because diagonal movement can reduce both differences simultaneously.
A useful rule to remember:
The central idea of A*¶
The heuristic h helps A* focus the search toward the destination instead of expanding equally in every direction.
Study record
| Field | Value |
|---|---|
| Attempts | 1 |
| Mastery | ❚ |
| The Latest Attempt | September 3, 2026 |
Python solution¶
import heapq
class Solution:
def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:
self.l = len(grid)
if grid[0][0] or grid[self.l - 1][self.l - 1]:
return -1
moves = [
(-1, 0),
(1, 0),
(1, 1),
(-1, -1),
(0, 1),
(0, -1),
(1, -1),
(-1, 1)
]
minHeap = [
(1 + self.dist((0, 0)), 1, (0, 0))
]
minDist = [
[float('inf')] * self.l
for _ in range(self.l)
]
minDist[0][0] = 1
while minHeap:
curDist, steps, curNode = heapq.heappop(minHeap)
if steps > minDist[curNode[0]][curNode[1]]:
continue
if curNode == (self.l - 1, self.l - 1):
return steps
for move in moves:
nextNode = (
curNode[0] + move[0],
curNode[1] + move[1]
)
if (
0 <= nextNode[0] < self.l
and 0 <= nextNode[1] < self.l
and not grid[nextNode[0]][nextNode[1]]
):
newSteps = steps + 1
if newSteps < minDist[nextNode[0]][nextNode[1]]:
minDist[nextNode[0]][nextNode[1]] = newSteps
newLen = newSteps + self.dist(nextNode)
heapq.heappush(
minHeap,
(newLen, newSteps, nextNode)
)
return -1
def dist(self, point):
return max(
abs(self.l - 1 - point[0]),
abs(self.l - 1 - point[1])
)