Graph Pathfinding Algorithms: A Comprehensive Guide

Graph Pathfinding Algorithms

Introduction: Pathfinding in graph theory refers to the process of finding a route between two nodes in a graph, typically optimizing for some cost (such as distance or time). In many cases, this means finding the shortest path from a start node to a target node. Graphs can be unweighted or weighted, which affects how path costs are measured. In an unweighted graph, every edge is considered equal (you might count each edge as a “hop”), so the shortest path is the one with the fewest edges. In a weighted graph, each edge has an associated weight or cost, and the shortest path is the one with the minimum total weight. Edge weights can represent anything from physical distance, to travel time, to financial cost. The presence of negative weights (edges with negative cost values) adds complexity: while an edge with a negative weight can make some paths cheaper, it also risks creating a negative cycle. A negative cycle is a loop whose total weight sum is negative, allowing indefinite traversal to decrease the path cost without bound. If a negative cycle is reachable, there is effectively no well-defined shortest path (the cost can always be lowered by looping), so algorithms must be able to detect such situations. Finally, some pathfinding methods use heuristics – educated guesses of remaining cost – to guide the search. These informed search algorithms (like A*) prioritize exploring paths that appear more promising (for example, those heading toward the goal), which can dramatically speed up finding a solution. However, heuristics must be carefully designed (they should not overestimate the true remaining cost) to ensure the found path is still optimal.

How and When to Use Each Graph Pathfinding Algorithm

Pathfinding algorithms are essential tools in graph theory and computer science, each suited to different conditions:

BFS (Breadth-First Search) is perfect for unweighted graphs or unit-cost scenarios, guaranteeing the shortest path in terms of edge count. It’s fast and uses minimal memory, making it great for simple pathfinding like maze solving or social network degrees of separation.
Dijkstra’s Algorithm handles arbitrary positive weights efficiently, making it the workhorse for routing problems (road networks, networking, etc.) where all costs are non-negative. It yields optimal paths and is generally faster than methods that handle negative edges.
Bellman-Ford is the choice when edges can have negative weights or when you need to detect negative cycles. It sacrifices speed for that generality. It’s useful in certain network algorithms and in any case where costs might decrease along a path.
A* combines the best of both worlds (speed and optimality) by using heuristics to guide the search. With a well-chosen heuristic, it finds optimal paths much faster than uninformed searches, which is why it’s the de facto algorithm in game AI, robotics, and other domains where a heuristic is available.
Greedy Best-First Search uses a heuristic too, but only in a greedy manner. It’s even faster and lighter than A* in many cases, but since it doesn’t ensure optimality, it’s used when a “good enough” quick solution is acceptable or as an exploratory technique.
IDA* provides an alternative when memory is at a premium. It will still find an optimal path (given an admissible heuristic) like A*, but by using iterative deepening, it dramatically lowers memory usage at the cost of some extra computations.

Choosing the right pathfinding algorithm depends on the problem constraints. If you know all weights are equal, BFS is simplest. If weights vary but are non-negative, Dijkstra’s or A* (if you have a target and a heuristic) are efficient. If you might have negative weights, Bellman-Ford is the safe bet. And if you’re working in an environment where memory is the bottleneck, consider IDA*. By understanding these algorithms, their requirements, and their performance characteristics, you can apply the optimal approach to a wide range of real-world graph pathfinding problems.

The Algorithms Guide

This article is part of a comprehensive guide about algorithms. To access the main article and read about other types of algorithms, from sorting to machine learning, follow the following link:

A Friendly Guide to Computer Science Algorithms by Category.

About This Article

This article will explore several fundamental pathfinding algorithms, organized by category. We’ll start with the classic method for unweighted graphs, then cover algorithms for weighted graphs (including those that handle negative weights), and finally discuss heuristic or informed search algorithms that use domain-specific knowledge to improve efficiency. For each algorithm, we’ll explain how it works, the data structures it uses, its time and space complexity, and practical use cases. Pseudocode or step-by-step outlines are provided where helpful for clarity.

Graph Traversal

If you’re looking for Graph Traversal solutions rather than pathfinding, go to the following article: Graph Traversal Algorithms: A Comprehensive Guide.

Searching Graphs

Understanding Graph based search is an invaluable skill when dealing with Graph-based algorithms. Learn more about these techniques and algorithms following this link: Graph-Based Search Algorithms.

Unweighted Graph Pathfinding (Shortest Path in Unweighted Graphs)

When all edges in a graph are unweighted (or effectively have the same weight), the shortest path between two nodes is the path with the fewest edges (the minimum number of “hops”). A classic algorithm for finding shortest paths in an unweighted graph is Breadth-First Search (BFS). BFS is an uninformed graph traversal algorithm that expands outward from the start node in waves (layers), ensuring that the first time we reach a node, it has been via the shortest possible path.

Breadth-First Search (BFS)

How it works: BFS explores the graph level by level. It starts at the source node and visits all of its immediate neighbors, then the neighbors of those neighbors, and so on. This layered approach guarantees that we find the shortest route (in terms of number of edges) to the target. BFS uses a queue data structure to manage the frontier of exploration. The algorithm maintains a set of visited nodes to avoid processing any node more than once (preventing infinite loops in graphs with cycles).

Algorithm steps (BFS):

Initialize: Enqueue the starting node and mark it as visited. You may also keep a predecessor map to reconstruct the path later (each visited node stores the node it came from).
Explore layer by layer: While the queue is not empty, dequeue the front node u. For each neighbor v of u that has not been visited yet, mark v as visited, record u as its predecessor, and enqueue v.
Termination: If you dequeued the target node at any point, you have found the shortest path to it (you can then reconstruct the path using the predecessor map). Otherwise, continue until the queue is empty (in which case the target is unreachable).

BFS ensures that the first time you encounter the goal node, you have traveled the minimum number of edges to get there. This is because all shorter paths would have been explored in earlier layers. Time complexity of BFS is O(V + E) (linear in the number of vertices and edges) in adjacency list representation. Space complexity is O(V) for the queue and visited set (in the worst case, you might enqueue every vertex). BFS is highly efficient for large unweighted graphs and will find the shortest path if one exists.

Use cases: BFS is ideal in scenarios where each move or connection has equal cost. For example, finding the minimum number of jumps to solve a puzzle, or the fewest links between two people in a social network (the “degrees of separation” problem). It’s also used in network broadcasting (finding nodes within a certain number of hops) and as a subroutine in more complex graph analyses (like finding connected components or checking bipartiteness). Whenever you need the shortest path in terms of steps (and not concerned with different weights), BFS is the go-to algorithm.

(Note: While Depth-First Search (DFS) can also find a path between nodes, it does not guarantee the shortest path in an unweighted graph. BFS is preferred for shortest-path problems in unweighted graphs because its layer-by-layer expansion naturally finds the minimum-hop solution.)

Weighted Graph Pathfinding (Shortest Path in Weighted Graphs)

In many real-world graphs, edges carry weights that are not all equal. For instance, a road network might have distances or travel times as weights on the roads. In weighted graphs, “shortest path” refers to the path with the least total weight. Two fundamental algorithms for single-source shortest paths in weighted graphs are Dijkstra’s Algorithm and the Bellman-Ford Algorithm. Dijkstra’s algorithm efficiently handles graphs with non-negative weights, while Bellman-Ford can accommodate negative weight edges (and can detect negative cycles).

Dijkstra’s Algorithm

How it works: Dijkstra’s algorithm finds the shortest path distances from a starting node to all other nodes in a graph with non-negative edge weights. It can also be used to find the shortest path to a single target node by stopping early once that target’s shortest distance is determined. The algorithm uses a greedy strategy combined with relaxation of edges (a process of progressively updating distance estimates). The key data structure used is a priority queue (min-heap) that stores nodes by their current shortest-known distance from the start.

Algorithm outline (Dijkstra):

Initialize distances: Set the distance to the source node as 0 and to every other node as infinity (or a very large number). Keep an array or map dist[] of these distances. None of the nodes have been finalized yet.
Priority queue setup: Insert the source node into a min-priority queue with priority equal to its distance (0). The priority queue will always yield the next node with the smallest tentative distance.
Iterative relaxation: While the priority queue is not empty, extract the node u with the minimum current distance. This distance is the shortest path to u (greedy choice). Mark u as finalized (visited). For each neighbor v of u with edge weight w (for edge u → v):
- If going through u offers a shorter path to v (i.e., if dist[u] + w < dist[v]), then update dist[v] = dist[u] + w and insert or update v in the priority queue with the new distance.
Termination: The algorithm continues until all reachable nodes have been finalized (or until the target node is removed from the queue, if you stop early for a single destination). The dist[] values now represent the shortest path distances from the source to every node. If a predecessor map is maintained (updating each neighbor’s predecessor when its distance improves), you can reconstruct the actual shortest path routes.

Dijkstra’s algorithm guarantees the optimal distances for graphs with non-negative weights because once it “locks in” (finalizes) a distance for a node by removing it from the queue, that distance is the smallest possible. If negative weights existed, this guarantee would break (a shorter path could appear later), which is why Dijkstra’s is restricted to non-negative edge weights.

Data structures: The algorithm relies on a min-priority queue (min-heap) to always pick the next closest node to process. Each entry in the queue is a node along with the current best distance found for it. Additionally, an array or dictionary for distances is used, and an optional predecessor map for path reconstruction.

Complexity: Using a binary heap priority queue, Dijkstra’s algorithm runs in O((V + E) log V) time, which is often written as O(E log V) for large graphs (since each edge insertion/relaxation involves a log V heap operation in the worst case). In dense graphs or with a simple array instead of a heap, it can degrade to O(V^2). Space complexity is O(V + E) to store the graph and O(V) extra for distances and queue (the queue can contain each vertex at most once at a time, though with updates some implementations push duplicates until they’re processed). In practice, Dijkstra’s is very efficient for moderate to large graphs without negative weights.

Use cases: Dijkstra’s algorithm is widely used in real-world routing and navigation problems. For example, mapping services (like GPS navigation systems) use variations of Dijkstra to find the shortest driving route between locations (road lengths or travel times are edge weights). Network routing protocols such as OSPF (Open Shortest Path First) use Dijkstra’s algorithm to compute shortest paths for data packet routing (treating link costs as weights). It’s also used in various optimization and scheduling problems where a cumulative cost needs to be minimized. Whenever you have a graph of positive costs and need the most cost-effective path, Dijkstra’s algorithm is a reliable choice.

Bellman-Ford Algorithm

How it works: The Bellman-Ford algorithm is another single-source shortest path algorithm that extends to graphs with negative edge weights. Unlike Dijkstra’s greedy approach, Bellman-Ford uses a dynamic programming approach that relaxes all edges in the graph repeatedly. It does not use a priority queue; instead, it systematically iterates, allowing distances to gradually improve. Bellman-Ford is slower than Dijkstra’s on positive-weight graphs, but it has the crucial ability to detect negative weight cycles and still compute correct shortest paths if negative weights are present (as long as there is no negative cycle reachable from the source).

Algorithm outline (Bellman-Ford):

Initialize distances: Similar to Dijkstra, set the start node’s distance to 0 and all others to infinity initially.
Relax edges repeatedly: Perform V-1 iterations (where V is the number of vertices). In each iteration, go through every edge (u, v) with weight w in the graph:
- If dist[u] + w < dist[v], then update dist[v] = dist[u] + w.
- This process is called edge relaxation, and by repeating it, shorter paths propagate through the graph. After V-1 iterations, all shortest paths (that do not involve a cycle) will have been found, because the longest possible shortest path uses V-1 edges (in a graph of V vertices, a simple path can have at most V-1 edges).
Negative cycle check: Optionally (and typically), add one more iteration over all edges. If any edge (u, v) still satisfies dist[u] + w < dist[v] at this point, it means a shorter path was found beyond V-1 edges, which can only happen if there’s a cycle with overall negative weight. In that case, a negative cycle exists, and the algorithm can report it (the concept of shortest path is undefined if such a cycle is reachable, because you could loop and keep reducing cost indefinitely).

After these steps, the dist[] array holds the shortest path cost to each reachable vertex (or an indication that a negative cycle exists). If a predecessor pointer is recorded during relaxations (updating when distances improve), you can reconstruct the actual paths as well.

Complexity: Bellman-Ford runs in O(V * E) time in the worst case, because it relaxes all E edges for each of the V-1 iterations (and an extra iteration for cycle check). This is considerably slower than Dijkstra for large graphs, especially if E is large or on dense graphs (where E is on the order of V^2). Space complexity is O(V) for the distance array (plus O(E) to store the edges if the graph isn’t already in memory). In practice, Bellman-Ford is used only for specific scenarios because of its slower performance.

Use cases: The primary advantage of Bellman-Ford is handling negative weights and detecting negative cycles. It’s historically used in certain network routing protocols—most notably the Distance-Vector routing protocols like RIP (Routing Information Protocol). In those, each router iteratively updates distances to destinations based on information from neighbors, which conceptually mirrors Bellman-Ford’s relaxation rounds. Bellman-Ford is also useful in domains like finance or economics for arbitrage detection: if the graph’s vertices represent currencies and edges represent exchange rates with negative log weights, a negative cycle indicates an arbitrage opportunity (profit loop). More generally, if you suspect negative edge costs in your problem (for example, profits or energy regeneration that effectively subtract cost), Bellman-Ford is the safe choice to find shortest paths. If no negative edges are present, however, one would prefer faster algorithms like Dijkstra’s.

Note: If a graph has negative cycles reachable from the source, typically no shortest-path solution is defined (since you can loop to get ever-lower cost). In such cases, Bellman-Ford will detect a negative cycle. Depending on the application, you might then report that no well-defined shortest path exists, or handle it specially (e.g., in arbitrage, report the opportunity).

Heuristic and Informed Search (Guided Pathfinding with Heuristics)

Uninformed algorithms like BFS, Dijkstra, and Bellman-Ford explore the graph without any knowledge of the target’s location beyond what the graph provides. In contrast, heuristic (informed) search algorithms use additional information – a heuristic function – to guide the search more directly toward the goal. A heuristic is typically an estimate of the remaining cost or distance from a given node to the target. By using a heuristic, these algorithms aim to explore fewer nodes than an uninformed search would, thereby finding the path faster in many cases. The trade-off is that the heuristic needs to be chosen carefully: if it’s too optimistic or not well-behaved, the algorithm might find a suboptimal path or even miss the solution.

The most important heuristic pathfinding algorithm is A* (A-star), which balances the actual cost so far and the heuristic estimate to ensure an optimal solution (given a good heuristic). We’ll also discuss Greedy Best-First Search, which is a simpler heuristic method that focuses solely on the heuristic (often faster but not guaranteed optimal), and briefly mention IDA* (Iterative Deepening A*), a variant of A* that uses less memory by trading some additional computations.

A* Search Algorithm

How it works: A* search is an extension of Dijkstra’s algorithm that integrates a heuristic estimate of the distance to the goal. For each node n, A* maintains two values:

g(n): the cost of the path from the start node to n (this is known from the search so far).
h(n): the heuristic estimate of the cost from n to the goal (this is provided by a heuristic function specific to the problem).
f(n) = g(n) + h(n): the estimated total cost of the path from start to goal going through n. A* uses f(n) as the priority for selecting the next node to explore.

The algorithm uses a priority queue (open set) ordered by the lowest f(n) value, ensuring that it always expands the node that appears most promising (lowest estimated total cost). It also keeps a closed set (or visited set) of nodes that have been fully processed, to avoid redundant work.

Algorithm outline (A):*

Initialize: Start by computing h(start) for the start node and set g(start) = 0. Set f(start) = h(start). Put the start node in the open priority queue with priority f(start). Initialize an empty closed set.
Expansion loop: While the open queue is not empty, remove the node u with the smallest f(u) value. If u is the goal node, A* terminates – you have found the lowest-cost path to the goal (because A* ensures that the first time you dequeue the goal, it’s optimal).
- Otherwise, add u to the closed set and examine each neighbor v of u. Let the weight of edge u → v be w. Compute a tentative cost g_temp = g(u) + w – this is the cost to reach v via u.
- If g_temp < g(v) (i.e., we found a cheaper path to v than any known before), update g(v) = g_temp. Compute h(v) (using the heuristic function for v to goal) and set f(v) = g(v) + h(v). If v is not already in the open queue or closed set, add it to the open queue with priority f(v). If it is already in the open queue with a higher old cost, update its priority to the new lower f(v). (If v is in the closed set but a better path is now found, in standard A* with a consistent heuristic this shouldn’t happen; with an inconsistent heuristic, one might need to remove it from closed and re-open it.)
Continue: Repeat this process, expanding nodes in order of increasing f value. The algorithm terminates when the goal is expanded (dequeued) or the open set becomes empty (meaning no path exists).

Heuristic design: The effectiveness of A* depends on the quality of the heuristic h(n). The heuristic should be admissible – meaning it never overestimates the true cost from n to the goal (it’s always a lower bound on the actual remaining cost). Admissibility guarantees that A* will find an optimal path. A common example of an admissible heuristic is straight-line distance in a navigation problem (as the crow flies distance, which is never more than the actual road distance). The heuristic should ideally also be consistent (monotonic), which means for every edge (u, v) with cost w, we have h(u) ≤ w + h(v). Consistency ensures that the f(n) values never decrease along a path, which simplifies the algorithm (no need to reopen closed nodes). Many admissible heuristics used in practice (like distances in metric spaces) are also consistent.

Data structures: A* typically uses structures similar to Dijkstra’s: a priority queue for the open set (ordering by f value instead of just g), a map or array for g-costs, and sets or flags for closed nodes. Optionally, like other searches, a predecessor map can be kept to reconstruct the final path once the goal is reached.

Complexity: The time complexity of A* can vary greatly depending on the heuristic. In the worst case, if the heuristic is poor (for example, h(n) = 0 for all nodes, which reduces A* to Dijkstra’s algorithm), the complexity is O(E log V) similar to Dijkstra’s. If the heuristic is very effective, A* explores far fewer nodes than Dijkstra’s would, often making it much faster on average. In many practical scenarios (like grid pathfinding with a good heuristic), A* runs almost linear in the path length (significantly pruned search space). However, in the worst-case scenario (especially if the state space is huge and the heuristic provides little guidance), A* could approach exponential time complexity because it might still have to explore a large portion of the graph. Space complexity is a consideration as well: A* stores all generated nodes in memory (open and closed sets). This can be a limiting factor for very large searches, as A* might use a lot of memory if many nodes are explored. Despite the theoretical worst-case, A* is usually the algorithm of choice for pathfinding in practice when a good heuristic is available, due to its excellent average-case performance.

Use cases: A* is widely used in applications where a specific target needs to be reached and we have domain knowledge to guide the search. The classic use case is in video games and robotics for navigating an agent or robot to a goal location on a map. For example, A* will efficiently compute a path for a game character around obstacles on a grid, using heuristics like Manhattan distance (for grid with orthogonal moves) or Euclidean distance (for more continuous movement) to guide the search. A* is also used in puzzle solving (like the 8-puzzle or 15-puzzle in AI) where the heuristic might be the number of misplaced tiles or sum of Manhattan distances of tiles from their goal positions – A* can find the minimum moves solution. In routing software (like driving directions), A* is often employed with heuristics such as straight-line distance or driving time estimates to focus the search towards the destination, making it faster than exploring all possible roads. Overall, A* provides an optimal path quickly by leveraging heuristics, making it a powerful algorithm whenever such heuristics can be defined.

Greedy Best-First Search

How it works: Greedy Best-First Search (GBFS) is another informed search strategy that uses a heuristic, but in a more naive way than A*. In Greedy BFS, the evaluation function for each node is simply f(n) = h(n) – in other words, it always expands the node that it thinks is closest to the goal (the smallest heuristic distance), ignoring the cost accumulated so far. This can be thought of as A* with g(n) set to 0 for all nodes (only considering the estimated remaining cost). The algorithm uses a priority queue ordered by the heuristic value h(n).

Algorithm steps (Greedy BFS):

Initialize: Compute h(start) for the start node, then put the start node in a priority queue (open list) with priority = h(start). Mark the start as visited.
Expand according to heuristic: While the queue is not empty, dequeue the node u with smallest h(u) (i.e., that appears closest to the goal in estimation). If u is the goal, return the path found (or report success). Otherwise, for each neighbor v of u:
- If v has not been visited (or processed) before, mark it and add it to the priority queue with priority h(v).
Continue: Repeat the process until the goal is reached or the queue empties (no solution). The search always picks the locally most promising node to explore next, according to the heuristic.

Characteristics: Greedy Best-First Search is greedy because it chooses what seems best in the short term (closest to the goal) and does not reconsider that choice. It does not guarantee an optimal path – in fact, it doesn’t even guarantee it will find a path in some tricky cases. Because it ignores the distance already traveled, it might bypass the true shortest path if that path involves going a little out of the way early on. Greedy BFS can also become stuck if it follows a heuristic “dead-end” – for example, going toward the goal into a cul-de-sac; if not implemented with a proper visited set, it might loop or fail. In practice, one usually still uses a visited set (closed set) to avoid revisiting nodes and to ensure termination on finite graphs. With that, Greedy BFS will find a path if one exists (it is complete in finite graphs when avoiding revisiting nodes), but the found path may be longer than optimal.

Complexity: The time complexity is difficult to characterize precisely since it depends on the heuristic’s guidance. In the worst case, Greedy BFS could still end up exploring a large portion of the graph (for instance, if the heuristic is misleading). It tends to expand fewer nodes than BFS or Dijkstra if the heuristic is reasonably good, often making it faster (hence its appeal). Each node is processed essentially once (plus neighbors checks), so a rough upper bound is O(E log V) due to the priority queue operations, similar to A*. Space complexity is O(V) for storing the queue and visited nodes.

Use cases: Greedy Best-First Search can be useful when you need a quick route that doesn’t have to be the optimal one. It’s sometimes used in AI as a baseline or when the heuristic is believed to be very accurate such that the first found path is probably good enough. For example, in pathfinding for games where speed is more critical than path optimality, a greedy approach might be acceptable if the levels are designed such that a straight-line heuristic almost always gives a near-best path. It’s also conceptually simpler, so it’s easy to implement for scenarios like maze solving by always moving roughly toward the goal. However, because of its pitfalls (potentially getting stuck or finding poor paths), Greedy BFS is often supplemented or replaced by A* in most serious applications where an optimal or at least reasonable path is needed. Think of Greedy BFS as “heuristic hill-climbing” towards the goal – fast and frugal, but not foolproof.

IDA* (Iterative Deepening A*)

How it works: A* can use a lot of memory because it keeps all options in the open set. Iterative Deepening A* is a variant that reduces memory usage by combining the heuristic guidance of A* with the memory-frugal nature of Depth-First Search. IDA* performs a series of depth-first searches that progressively increase a cost-bound. It uses the A*’s f(n) = g(n) + h(n) evaluation but instead of a global open set, it does a depth-first exploration up to a threshold of f cost, and if the goal is not found within that bound, it increases the threshold and starts again.

Algorithm sketch (IDA):*

Perform a depth-first search from the start node, but keep track of the cumulative cost g(n) and only proceed down a path as long as g(n) + h(n) ≤ B, where B is the current threshold bound.
If the goal is found during this DFS (with cost ≤ B), return it.
If the DFS finishes without finding the goal, determine the smallest f(n) value that exceeded the bound (i.e., the next promising threshold), let’s call it B_new.
Set B = B_new and restart the depth-first search from the start.
Repeat until the goal is found (or no new nodes to expand, implying no solution).

Each iteration deepens the allowed search boundary based on heuristic estimates. Essentially, it’s like doing depth-first search with a limit on the estimated path cost rather than on depth alone. Because it uses DFS (which only needs to store the recursion stack), memory usage is dramatically reduced compared to standard A*, at the cost of possibly revisiting nodes multiple times across iterations.

Complexity: The time complexity of IDA* depends on how effectively the heuristic guides the search and how finely the threshold increases. In many cases, the overhead of repeated searches is not too bad because the threshold typically jumps in such a way that the last iteration does most of the work (previous iterations serve to gradually get there). In the worst case, IDA* could end up doing a lot of repeated exploration, making it slower than A* by a constant factor or more. However, if memory is a critical constraint, IDA* may find solutions where A* cannot run at all due to memory exhaustion. The space complexity of IDA* is O(d) where d is the depth of the solution, because at any time it’s essentially doing a DFS (plus some minor bookkeeping). This is a huge improvement over A*’s memory usage, which can be O(V) in the worst case.

Use cases: IDA* is famously used in solving puzzles with large state spaces – a classic example is the 15-puzzle (sliding tile puzzle). In such puzzles, the branching factor is high and the state space is enormous, so A* (even with a good heuristic like Manhattan distance) might require too much memory to store all those states. IDA* with the same heuristic can often find the optimal solution while using memory comparable to DFS, making it feasible to solve problems like the 15-puzzle optimally. Another scenario is any pathfinding on a huge implicit graph (for example, a combinatorial puzzle or game state space) where storing all visited states is impractical; IDA* allows the search to go deep without blowing up memory. The trade-off is that it might revisit states, but with a strong heuristic, this re-exploration is limited. In summary, IDA* is useful when you need A*-like optimality but cannot afford A*’s memory consumption.

Aside: Other memory-efficient A variants exist as well, such as SMA* (Simplified Memory-Bounded A*), which tries to keep the best partial paths within a fixed memory limit. IDA is one of the simpler and more widely used approaches for memory-constrained search.