Introduction

Calculating the shortest path between two points in a grid is a common problem in computer science and mathematics, with applications across robotics, navigation systems, and computer graphics. The problem involves finding the minimum number of steps required to move from a starting point to a destination, usually within a grid of cells, with or without obstacles. Popular algorithms used to solve this problem include Dijkstra's algorithm, A* (A-star), and Breadth-First Search (BFS).

Grid Representation

A grid is often represented as a 2D matrix where each cell can either be empty (allowing movement) or blocked (acting as an obstacle). For example, consider a grid:

• Orthogonal movement: Movement can only occur horizontally or vertically, not diagonally.
• Diagonal movement: Movement can occur in eight directions — up, down, left, right, and the four diagonals.
• Suitability: BFS is suitable for unweighted grids where each move has the same cost.
• Approach: BFS explores all neighbors at the present depth before moving on to nodes at the next depth level, effectively finding the shortest path in an unweighted grid.
• Suitability: Ideal for weighted grids where different movements may have different costs.
• Approach: Utilizes a priority queue to explore the least costly path first, ensuring the smallest cumulative cost to each node before moving onward.
• Maintains cumulative costs rather than steps.
• Efficiently finds shortest path in weighted graphs where all weights are non-negative.
• Suitability: Used where heuristic information (such as Euclidean or Manhattan distance to the end) is valuable.
• Approach: Combines aspects of Dijkstra’s algorithm and greedy best-first search through a heuristic to estimate the cost to reach the target, often leading to faster results than Dijkstra's for complex grids.
• Faster than plain Dijkstra due to heuristic guidance.
• Best suited for environments where predictive insights are available.
• V: Number of vertices.
• E: Number of edges or possible moves.