What is a shortest path?
A shortest path between two nodes is the sequence of edges connecting them that uses the fewest hops possible — or, in a graph where edges carry weights, the sequence whose total weight is lowest, which isn’t always the same as the sequence with the fewest edges. Between any two nodes that sit in the same connected component, there might be dozens of different sequences of edges linking them, but only the one, or ones tied for the minimum, count as a shortest path, and that number is one of the most fundamental ways to describe how far apart two nodes really are within a graph‘s structure.
What’s the difference between “fewest edges” and “lowest total weight”?
In an unweighted graph, where every edge is treated as equivalent, the shortest path is simply the one that uses the fewest edges — hop count and path length mean the same thing. Finding it is a well-understood problem: starting from one node and expanding outward one layer of neighbors at a time, marking each newly reached node with the number of hops it took to get there, correctly finds the shortest hop-count path to every reachable node in the graph.
Once edges carry weights — as they do in a proximity graph, where an edge’s weight is effectively the distance between the two vectors it connects — the calculus changes. A path with more hops can have a lower total weight than a path with fewer hops, if the fewer-hop path happens to route through edges that are individually much longer. In a weighted graph, “shortest” means lowest total weight along the path, not fewest edges, and finding it generally requires an algorithm that always expands the currently-cheapest known path first rather than simply expanding outward hop by hop. This distinction matters enormously for a proximity graph, because the entire reason edges carry weights at all is to capture something meaningful about the space being searched — pretending every edge is equally “long” would throw away exactly the information a nearest-neighbor search actually needs.
Does HNSW’s search actually compute the shortest path to the query?
It’s worth being precise here, because this is a point of real confusion: HNSW‘s greedy search does not compute an exact shortest path in the formal sense used by shortest-path algorithms, and it isn’t trying to. A true shortest-path algorithm explores broadly enough to guarantee it has found the provably minimal-weight route between two specific nodes, which requires the kind of systematic, exhaustive-within-reason exploration that a full shortest-path algorithm performs. HNSW‘s search, by contrast, makes locally greedy decisions — from wherever it currently is, move toward whichever neighbor looks closest to the query — with no formal guarantee of ever discovering the exact minimal-distance path from an entry point to the true nearest neighbor. It’s an approximate strategy, and the “approximate” in approximate nearest-neighbor search is a direct acknowledgment of exactly this gap.
What HNSW’s construction process cares about instead is a related but distinct property: keeping the graph’s diameter — the longest of the shortest paths between any pair of reachable nodes — small relative to the number of nodes in the graph. A small diameter means that even though the search isn’t guaranteed to find the true shortest path to any particular target, a genuinely short path does exist for the greedy search to have a realistic chance of finding, and the hierarchy of layers that gives HNSW its name exists specifically to help the search discover a short route quickly rather than wander through a large fraction of the graph before converging.
Why does the concept of a shortest path still matter if HNSW doesn’t compute one exactly?
Shortest path is one of those foundational graph-theory ideas that matters for HNSW indirectly rather than directly — it’s the yardstick used to describe and reason about the graph’s overall navigability, even though the search algorithm running on top of that graph doesn’t compute it explicitly for every query. When people describe HNSW, or the small-world graphs it builds on, as having “logarithmic” search behavior, what’s really being claimed is that shortest paths between arbitrary nodes tend to stay short — proportional to the logarithm of the number of nodes — even as the graph grows very large, and that a greedy search operating on a well-constructed graph has a good chance of tracing something close to that short path without needing to compute it exactly. The theoretical arguments for why HNSW should behave efficiently at scale lean directly on this property of the underlying graph, even though the practical search algorithm itself is a much simpler, greedy procedure rather than a formal shortest-path solver.
Having drawn the distinction between an exact shortest path and the greedy approximation HNSW’s search actually performs, the graph diameter glossary page is the natural next stop, since it’s the aggregate version of this same idea — the worst-case shortest path across the whole graph rather than between one specific pair of nodes. From there, the greedy navigation and best-first search glossary entries look at the actual traversal strategy HNSW uses in place of computing exact shortest paths, and why that trade-off turns out to work well in practice despite offering no formal guarantee.