When to Use What: Trade-offs

Both Dijkstra and A* find optimal paths. But they have different strengths. Knowing when to use each one helps you write better code.

When Dijkstra is Better

Multiple Goals

Scenario: You need paths from one source to many destinations.

Example: Finding distances from your location to all restaurants in a city.

Why Dijkstra: It naturally finds paths to all nodes. Run it once, get all distances.

A alternative:* You’d need to run A* separately for each goal, which is slower.

Unknown Goal Location

Scenario: You don’t know where the goal is, or there are many possible goals.

Example: Finding the nearest hospital from your location.

Why Dijkstra: Explores outward until it finds any valid goal. A* needs a specific goal to compute the heuristic.

No Good Heuristic

Scenario: You can’t easily estimate distance to goal, or the heuristic would be expensive.

Example: Complex terrain where straight-line distance isn’t meaningful.

Why Dijkstra: Doesn’t need a heuristic, so it works in any scenario.

All-Pairs Shortest Paths

Scenario: You need distances between all pairs of nodes.

Example: Precomputing a distance matrix for a game map.

Why Dijkstra: Run it from each node, or use Floyd-Warshall. A* isn’t designed for this.

When A* is Better

Single Known Goal

Scenario: You have one specific goal location.

Example: Navigation from point A to point B.

Why A:* Usually explores fewer nodes, so it’s faster.

Good Heuristic Available

Scenario: You can cheaply compute a reasonable distance estimate.

Example: Grid with Manhattan or Euclidean distance.

Why A:* The heuristic guides the search, reducing exploration.

Performance Matters

Scenario: You need the path quickly, and you’re doing many searches.

Example: Real-time game AI that needs to pathfind every frame.

Why A:* Fewer nodes explored = faster execution.

Memory Constraints

Scenario: You have limited memory, and exploring fewer nodes helps.

Example: Embedded systems or mobile devices.

Why A:* Explores fewer nodes, so uses less memory.

Decision Checklist

Use this checklist to choose:

Choose Dijkstra if:

• ✅ You need paths to multiple goals
• ✅ Goal location is unknown
• ✅ No good heuristic available
• ✅ You need all-pairs shortest paths

Choose A if:*

• ✅ You have a single known goal
• ✅ You have a good heuristic
• ✅ Performance is important
• ✅ Memory is constrained

Performance Comparison

Here’s a summary of how Dijkstra and A* compare on different scenarios:

Correctness Guarantees

Both algorithms guarantee optimal paths under certain conditions:

Dijkstra

• ✅ Optimal with non-negative edge weights
• ✅ Finds all shortest paths from source to all nodes
• ❌ Fails with negative weights (use Bellman-Ford instead)

A*

• ✅ Optimal with admissible heuristic and non-negative weights
• ✅ Finds optimal path to single goal
• ❌ May be suboptimal if heuristic is not admissible
• ❌ Fails with negative weights

Performance Characteristics

Dijkstra:

• Time: O((V + E) log V) with binary heap
• Space: O(V) for distances and queue
• Explores: Often explores many nodes, especially far from goal

A:*

• Time: O((V + E) log V) with binary heap (same worst case)
• Space: O(V) for distances and queue
• Explores: Usually fewer nodes than Dijkstra (depends on heuristic quality)

In practice: A* often explores 10-50% fewer nodes than Dijkstra for single-goal pathfinding.

Key Takeaways

Before moving forward:

1. Dijkstra for multiple goals - One run finds paths to all nodes
2. A for single goal* - Usually faster with good heuristic
3. Both are optimal - With right conditions (non-negative weights, admissible heuristic)
4. Heuristic quality matters - Better heuristic = fewer nodes explored
5. Consider your use case - Multiple goals? Unknown goal? Performance critical?

Quick Check

What’s Next?

Now that you understand when to use each algorithm, let’s see how to implement them. In the next page, we’ll walk through complete code implementations.