What is the difference between Dijkstra and A* (A-star)?

0-2 years experience

1. 1We need the shortest path on a small grid where every move costs the same. Would you pick Dijkstra or A*, and why?
2. 2If you run Dijkstra on a graph with all edge weights equal to 1, what does it compute compared to A* with a zero heuristic?
3. 3Imagine a simple navigation feature that only finds routes between two points with no traffic data. Which algorithm would you choose and what changes would you make to implement it?

2-5 years experience

1. 1Our game uses Dijkstra for pathfinding and is lagging with many agents on a large map. Walk me through how you'd refactor it to use A* and what pitfalls to watch for.
2. 2After switching to A* we observed some routes longer than the optimal ones. What could cause A* to return suboptimal paths compared to Dijkstra?
3. 3We have a pre‑computed straight‑line distance heuristic for each node. How would you integrate it into the search, and what trade‑offs does it introduce versus a pure Dijkstra approach?

5-8 years experience

1. 1Design a routing microservice that must handle millions of concurrent shortest‑path queries on a road network with dynamic traffic weights. How do you decide between Dijkstra, A*, or a hybrid, and how would you scale the solution?
2. 2Explain how you would modify A* to guarantee optimality when the heuristic is not admissible, and discuss the performance impact at scale.
3. 3Our system currently caches results of recent Dijkstra runs. If we switch to A*, what changes are needed in the cache invalidation strategy, and how does heuristic consistency affect cache hit rates?

8+ years experience

1. 1We are migrating a legacy navigation stack that uses Dijkstra to a new platform requiring real‑time routing with frequent updates and multiple vehicle types. Outline an architecture plan to gradually replace Dijkstra with A*, covering backward compatibility, testing, and long‑term maintainability.
2. 2Several teams rely on exact shortest‑path guarantees while others accept approximate routes for speed. How would you create a shared library or service that lets each team choose Dijkstra or A* with clear contracts, and what governance processes would you establish?