Graph Algorithms from Scratch — Shortest Paths and Where They Lead

In plain words: "the promise of vertex $n$, $f(n)$, is the distance actually walked from the start to $n$, $g(n)$, plus an estimate of the remaining distance from $n$ to the goal, $h(n)$." The function $h$ is called a heuristic. On a map, the classic choice is straight-line distance to the goal: roads may twist and turn, but they can never be shorter than the straight line, so this estimate never overestimates the true remaining distance.

As long as that never-overestimate property (called admissibility) holds, A* is guaranteed to find a shortest path — while exploring far fewer vertices than Dijkstra, because the search cone is bent toward the goal. And notice: set $h(n)=0$ and A* collapses back into Dijkstra exactly. Dijkstra is simply "A* with zero intuition" — the two are not different algorithms so much as two points on one continuum.

Dijkstra in code

With Python's heapq (a binary heap), the core is about ten lines:

import heapq

def dijkstra(graph, start):          # graph[u] = [(v, w), ...]
    dist = {start: 0}
    pq = [(0, start)]                # (tentative distance, vertex)
    while pq:
        d, u = heapq.heappop(pq)     # finalize the current minimum
        if d > dist.get(u, float("inf")):
            continue                 # stale entry — skip it
        for v, w in graph[u]:
            if d + w < dist.get(v, float("inf")):
                dist[v] = d + w      # relaxation
                heapq.heappush(pq, (d + w, v))
    return dist

To turn this into A*, change the key you push from d + w to d + w + h(v). The skeleton stays identical.

And on to vector search — HNSW as applied graph traversal

Now for the payoff. In RAG and recommendation systems, the beating heart is nearest-neighbor search: documents or products become embedding vectors, and every query asks "which stored vectors are closest to this one?" The brute-force answer — measure the distance to every vector — is fine until the collection reaches tens of millions, at which point a full scan per query stops being affordable.

This is where HNSW (Hierarchical Navigable Small World, proposed in the paper listed as this article's primary source) comes in. The idea: ahead of time, build a graph that connects each vector to its near neighbors. At query time, start at some entry vertex and repeat one move: "among my current vertex's neighbors, step to whichever is closest to the query." When no neighbor gets you any closer, you've arrived at a candidate answer. You are walking a graph guided by an estimate of closeness — a direct cousin of the idea behind A*.

The "H" is for hierarchy. HNSW stacks progressively sparser graphs on top of the base layer; a search takes long-range hops in the top layers to get roughly close, then descends layer by layer to fine-tune — like taking the highway to the right city, then surface streets to the exact address. (Data-structure fans will recognize the skip list.) In practice this finds neighbors with far fewer distance computations than a full scan. The catch: because the walk is greedy, it is an approximate method that can occasionally miss the true nearest neighbor. The standard countermeasure is to carry a beam of the best ef candidates instead of a single walker — and that ef knob is exactly what matters in production, as we'll see next.

The "closeness" being measured is inner product, cosine similarity, or Euclidean distance. You can build intuition for that ruler in the figure below.

How this is used in the field

When search or RAG engineers choose an index. Nearly every major vector database — Faiss, pgvector, Qdrant, Milvus, OpenSearch — ships an HNSW implementation. Three parameters do most of the work: M, the number of edges per vertex (memory vs. accuracy); efConstruction, the candidate-list size while building (index quality); and efSearch, the candidate-list size while querying (recall vs. latency). The standard tuning ritual is to sweep efSearch upward on real data and find where recall plateaus.

Pitfall 1: blaming the distance function for low recall. When RAG fails to retrieve an obviously relevant document, check whether efSearch (sometimes just ef) is still at its default before suspecting the embedding model. Misses are inherent to approximate search, and raising the candidate count often makes them vanish.

Pitfall 2: mismatched distance metrics. If you intend cosine similarity but feed unnormalized vectors into an inner-product index, the results skew toward whatever has the largest norm. "Does the metric at query time match the metric at build time?" belongs at the top of any incident checklist.

Pitfall 3: Dijkstra on negative weights. The moment someone models a discount or reward as a negative edge cost, the algorithm's premise collapses and it returns wrong answers without raising any error. If negative edges are part of the design, switch to the Bellman–Ford family.

For game and mapping engineers, reviewing whether an A* heuristic is admissible (never overestimates) is a required checkpoint. It is also a perennial interview question: "what happens if $h$ overestimates?" — answer: the search gets faster, but the shortest-path guarantee breaks.

Takeaways

• A graph is the universal language of "dots and lines," and the shortest path is its most important question
• BFS solves fewest-edges with a queue; Dijkstra solves weighted-shortest with a priority queue and relaxation
• A* bends the search toward the goal using an estimate that never overestimates; with $h=0$ it is Dijkstra
• HNSW greedily walks a graph of near neighbors, guided by closeness — the same graph-search skeleton, now holding up retrieval in the LLM era

For how to read the big-O notation used here, see the complexity basics; for queues and heaps themselves, the data structures tour; and for the full retrieval system HNSW plugs into, RAG fundamentals.