Graphs and Pathfinding

Pathfinding is a classic problem. It typically involves finding the shortest or cheapest path between two points. There are many algorithms to solve this problem, most of which are based on graphs with various modifications. Some algorithms are more effective than others, depending on the situation. Let's go through some of the most popular ones and discuss which algorithm is more effective in which scenario. We'll look at several commonly used algorithms: BFS, GBFS, Dijkstra, and A*.

Graph Quick Overview

Let's briefly recall what a graph is. A graph is a data structure consisting of vertices (nodes) connected by edges. The edges of a graph can have direction and different costs or weights. A graph can also have cycles.

           

Unweighted graph / Weighted graph / Directed graph

Representations

There are two common ways to represent a graph: an adjacency list and an adjacency matrix.
Adjacency list can be represented as a hash map where key represents a vertices and value is a list of it's neighbours.
Adjacency matrix is a 2D matrix[i][j] where [i][j] represents an edge between nodes i and j.

     

Adjacency list / Adjacency matrix

We will used adjacency matrix as it's good represents our 2D grid map with 4-directionally adjacent cells.

---

Breadth-First Search (BFS)

Breadth-first search (BFS) is so called because during the traversal it goes in breadth. It sequentially explores all the nodes starting from the root node one by one. When all nodes at a given level are explored, it moves to the next level, and so on until it reaches the target node.

BFS guarantees finding the shortest path in an unweighted graph because it explores all nodes level by level.

Algorithm

1. Initialize: Add the start node to a queue and mark it as visited.

2. Expand: Dequeue a node, process it, and enqueue its unvisited neighbors.

3. Repeat: Continue until the target node is found or the queue is empty.

Time and Space Complexity

• Time Complexity: O(V+E), where V is the number of vertices and E is the number of edges.

• Space Complexity: O(V) due to the queue and visited set.

Pros & Cons

✅ Pros:

• Guarantees the shortest path in an unweighted graph.

• Complete: Always finds a solution if one exists.

• Simple and easy to implement.

❌ Cons:

• Inefficient in large graphs due to high memory usage (stores all nodes at a given depth).

• Not optimal for weighted graphs since it doesn't consider edge weights.

• Time complexity is high.

Example

BFS explores nodes evenly, level by level, adding each node to a simple FIFO queue.

See the Pen Pathfinding. BFS by Viacheslav Demianov (@VyacheslavDemyanov) on CodePen.

---

Greedy Best-First Search (GBFS)

Greedy algorithms aimed to find best solution at each step. Each decision is made based only on the current context on each step, and ignores its impact on future or previous steps. It uses a priority queue (or min-heap). GBFS algorithm used heuristic function to proritize exploring nodes. In general, it's fast but not always optimal pathfinding in large spaces.

Algorithm

1. Initialize: Add the start node to a priority queue, using a heuristic for priority.

2. Expand: Dequeue the node with the lowest heuristic value and process it.

3. Enqueue: Add its unvisited neighbors to the queue, prioritizing lower heuristic values.

4. Repeat: Continue until the target node is found or the queue is empty.

Heuristic Function

Heuristic Function (h(n)) estimates the cost from a given node to the target node.

There are two most popular functions to calculate distance between two points:

Euclidean Distance:

• Works well when diagonal movement is allowed.

• Used in problems where movement is not restricted to grid-based paths.

Manhattan Distance:

• Works well when diagonal movement is not allowed.

• Works well for grid-based movement (e.g., chess, city streets, tile-based games).

Time and Space Complexity in a Graph

• Time Complexity: O(E), in the worst case, all edges are processed before finding the goal.

• Space Complexity: O(V) due to the priority queue and visited set.

Pros & Cons

✅ Pros:

• Faster than BFS and Dijkstra in many cases.

• Uses a heuristic to guide the search toward the goal.

• Can be memory efficient in some cases compared to BFS.

❌ Cons:

• Not optimal: It may get stuck in local optima.

• Incomplete in some cases (e.g., if the heuristic leads to an infinite loop).

• Performance heavily depends on the heuristic function.

• Can use a lot of memory due to deep searches.

Example

For GBFS we replaced the FIFO queue with a priority queue and use a heuristic function to calculate the path cost at each step. In some cases, this may lead to a non-optimal path.

See the Pen Pathfinding. GBFS by Viacheslav Demianov (@VyacheslavDemyanov) on CodePen.

---

Dijkstra

Dijkstra’s uses a weighted graph in a similar manner to a BFS to exhaust all possible routes and find the optimal route to the target node. Each edge carries a non-negative weighted value which represents some measurement, for example time or distance. Dijkstra always processes nodes in order of increasing distance, meaning that by the time a target node has been processed, the path to it is already the shortest.

Algorithm

1. Initialize: Set all distances to infinity, except for the start node (set to 0). Add all nodes to a priority queue.

2. Expand: Extract the node with the smallest distance, process it, and update its neighbors’ distances.

3. Relaxation: If a shorter path to a neighbor is found, update its distance and reinsert it into the queue.

4. Repeat: Continue until all nodes are processed or the target node is reached.

Time and Space Complexity in a Graph

• Time Complexity: O((V + E) log V) using a priority queue (heap).

• Space Complexity: O(V+E) using an adjacency matrix and simple iteration.

Pros & Cons

✅ Pros:

• Guaranteed to find the shortest path in weighted graphs with non-negative weights.

• Complete: Always finds a solution if one exists.

❌ Cons:

• Inefficient for large graphs.

• Can explore unnecessary nodes when compared to heuristics-based algorithms.

• Not suitable for negative weights.

Example

To illustrate Dijkstra's algorithm, I added a forest node that costs 3 points, whereas a normal node costs 1 point.

See the Pen Pathfinding. Dijkstra by Viacheslav Demianov (@VyacheslavDemyanov) on CodePen.

---

A* (Astar)

The A* (Astar) algorithm finds the shortest path from in a weighted graph while efficiently balancing exploration and cost. It improves upon Dijkstra’s by incorporating heuristics to guide the search toward the goal more efficiently. It combines the cost of reaching a node (like Dijkstra’s) with an estimated cost to the target, allowing it to prioritize promising paths.

Algorithm

• Initialize: Set all distances to infinity except for the start node (set to 0). Add the start node to a priority queue with a priority of f(n) = g(n) + h(n), where g(n) is the cost from the start to n, and h(n) is the estimated cost to the target.

• Expand: Extract the node with the smallest f(n), process it, and update its neighbors g(n).

• Heuristic: Use a heuristic function (e.g., Manhattan distance, Euclidean distance) to estimate the cost to the target.

• Relaxation: If a shorter path to a neighbor is found, update its g(n) and reinsert it into the queue with the updated priority.

• Repeat: Continue until the target node is reached or all possibilities are exhausted.

Time and Space Complexity

• Time Complexity: O((V + E) log V) in the worst case, similar to Dijkstra’s, but often faster in practice due to heuristic pruning.

• Space Complexity: O(V+E) due to storing node information in the queue and heuristic calculations.

Pros & Cons

✅ Pros:

• More efficient than Dijkstra’s in many cases due to heuristic guidance.

• Guarantees the shortest path if the heuristic is admissible and consistent.

❌ Cons:

• More complex to implement than Dijkstra’s.

• Can be computationally expensive for very large graphs.

Example

The priority queue now prioritizes nodes based on the sum of the path cost and the heuristic cost.

See the Pen AStar by Viacheslav Demianov (@VyacheslavDemyanov) on CodePen.

---

Which Algorithm to Choose?

We have taken a look at several popular algorithms for graph traversal and shortest path finding. Their field of usage is wide, for example:

• Game AI (NPC movement, pathfinding).

• Web crawlers and search engines.

• Logistics and GPS navigation.

• Social networks (finding the shortest connection between two users).

• Robotics (autonomous navigation).

• Network optimization (efficient data routing).

• And more.

While A* is often the best choice, there are cases where it’s not possible or where another algorithm is better. Here are a few situations:

• Memory Constraints

  • A* requires storing all visited nodes in memory, making it memory-intensive.

  • Example: Older 8-bit computers had limited RAM, making A* impractical for large maps.

  • Better Alternative: GBFS or a simplified BFS/Dijkstra variant with pruning.

• Dynamically Changing Environments

  • A* precomputes the best path based on static data. If the environment changes (e.g., new obstacles, moving units), it has to recompute from scratch, which is slow.

  • Example: In RTS games, units move in real time, and recalculating A* repeatedly is inefficient.

  • Better Alternative:

    • D-Lite (Dynamic A)* - an improved version that updates paths dynamically.

    • Hierarchical Pathfinding (HPA)* - breaks maps into chunks to speed up search.

• Large Graphs

  • A* needs to store many nodes in the priority queue, making it inefficient on massive graphs.

  • Example: In open-world games or real-world GPS navigation, a full A* search over a large map would be too slow.

  • Better Alternative:

    • Bidirectional A* - Searches from start and goal simultaneously, reducing explored nodes.

    • ALT (A with Landmarks)* - Uses precomputed heuristic data to speed up pathfinding.

• Unknown or Infinite Search Space

  • A* requires a known goal and a finite search space. If the map is infinite or unknown, it doesn’t work well.

  • Example:

    • Web Crawlers that explore the internet don’t have a fixed endpoint.

    • Procedurally generated worlds (e.g., Minecraft) where the map is built as you explore.

  • Better Alternative:

    • Iterative Deepening A (IDA)** - Uses depth-first search with a heuristic, reducing memory usage.

    • BFS/Dijkstra - If exploring an unknown space without a goal.

---

Final Thoughts

A* is powerful but not always the best. If you have low memory, dynamic environments, huge maps, unknown spaces, or real-time constraints, other algorithms work better.

All the code is available on GitHub.