Dijkstra's Algorithm vs. A* Search: Priority Queue Implementation & Admissible Heuristics
Implement lazy-deletion min-heap Dijkstra and A* search with Manhattan/Euclidean admissible heuristics.
Dijkstra's algorithm expands nodes ordered by path cost from the source g(u), guaranteeing optimal shortest paths on any graph with non-negative edge weights in O((V + E) log V). A* search orders the priority queue by f(u) = g(u) + h(u), using an admissible heuristic h(u) <= h*(u) to direct search toward the target while preserving optimality.
Interactive Runnable CodeSandbox
Lazy-Deletion Min-Heap Dijkstra Shortest Path
A* Evaluation Function & Admissibility Condition
When h(u) = 0, A* degenerates identically to Dijkstra's algorithm.
Step-by-Step Implementation Breakdown
Guard Against Stale Heap Entries with if d > dist[u]: continue
Since standard binary heaps lack O(log V) decrease-key, we push duplicate entries with smaller distances and skip outdated tuples when popped.
Verify Non-Negative Edge Weights Before Running Dijkstra
If negative edges exist, Dijkstra's greedy popped-node invariant breaks; use Bellman-Ford in O(VE).
Production Edge Cases & Interview Traps
- Unreachable vertices retain float('inf') in the distance array; convert to -1 when required by API contracts.
Frequently Asked Questions
What is the difference between an admissible and a consistent heuristic in A*?
Admissible means h(u) never overestimates the true remaining cost to goal; consistent (monotonic) means h(u) <= w(u, v) + h(v) (triangle inequality), guaranteeing nodes are never re-expanded.