Algorithm dossier

  • Category: Shortest path
  • Worst-case complexity: O(n log n)
  • Approach: Greedy
  • Data structure: Graph
  • First formalised: 1960s

Why this snippet is A* Search

**Why A*.** Same greedy-relaxation skeleton as Dijkstra, but the priority is f[u] + h(u) — the path cost *plus a heuristic estimate to the goal*. With an *admissible* h (never overestimates), A* is guaranteed optimal and dominates Dijkstra in practice by directing search toward t. Tell. The h.call(v) factored into the open-set priority is what makes this not-Dijkstra; if h were always 0, this code reduces to Dijkstra.

How to read a redacted algorithm

Algodle strips identifier names so the snippet has to be read for its shape: the control flow, the data structures it manipulates, the order in which it visits its input. Loops with two pointers crawling toward each other are usually search or partition. A recursion that splits its input in half and recurses on both halves is divide-and-conquer. A priority queue plus graph traversal is almost certainly Dijkstra, Prim, or A*. Six hint columns — category, complexity, approach, data structure, era — let you triangulate even when the snippet itself is opaque.