Graph Algorithms from Scratch — Shortest Paths and Where They Lead

From transit apps to vector search, the world runs on dots and lines. We build up BFS, Dijkstra, and A* assuming zero background, then follow one unbroken thread all the way to HNSW — the graph search powering retrieval in the LLM era.

Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs

The world is made of dots and lines

Picture a subway map. Stations are dots; the tracks connecting them are lines. The map ignores real distances and geography entirely — all it records is what connects to what. This structure, stripped down to pure connectivity, is what mathematicians call a graph. The dots are vertices (or nodes), the lines are edges.

Graphs go far beyond subway maps. Social networks (people are vertices, follows are edges), web pages and hyperlinks, road networks, atoms and chemical bonds, even the layers of a neural network — almost any "relationship between things" can be written as a graph. If the relationship has a direction (a follow is one-way), the graph is directed; otherwise it is undirected. If each edge carries a number like travel time or distance, it is a weighted graph.

The most fundamental — and most frequently asked — question about a graph is the subject of this article: the shortest path. "What is the cheapest way to get from A to B?" Car navigation, transit routing, enemy AI chasing you through a game level, and (as we'll see later) vector search all boil down to this one question.

"Shortest" comes in two flavors

There are actually two distinct versions of the problem:

• Minimize the number of edges: "the route with the fewest transfers." Every edge counts the same (cost 1).
• Minimize the total edge weight: "the fastest route." Each edge has its own cost.

BFS solves the first; Dijkstra's algorithm solves the second. Keep this distinction in mind and you'll never reach for the wrong tool.

BFS: search that spreads like ripples

Breadth-First Search (BFS) works like a stone dropped into a pond. From the starting point, you visit everything one step away, then everything two steps away, and so on — rings expanding outward in order of distance.

The only tool you need is a queue (a first-in, first-out waiting line). Put the start vertex in the queue; repeatedly take one out and append each unvisited neighbor, marking it as seen. That's the whole algorithm. Because the ripple expands in order of distance, the moment you first reach a vertex, the number of steps taken is already the shortest hop count to it. No shorter route can turn up later.

With $V$ vertices and $E$ edges, the cost is $O(V + E)$ — each vertex and edge is touched at most once, essentially linear time. Compare that with the naive approach of enumerating every possible path and picking the shortest: the number of paths explodes combinatorially, giving exponential time. Drag $n$ in the figure below to feel just how different those two regimes are.

Dijkstra's algorithm: locking in answers, cheapest first

Add weights to the edges and BFS breaks. A route with 2 edges totaling 10 minutes can lose to a route with 3 edges totaling 6 minutes — but BFS only counts edges. In a weighted world, "expand rings in order of nearness" still works, but "near" has to be re-measured in accumulated cost rather than step count.

Enter Dijkstra's algorithm, devised by Edsger Dijkstra in 1956. The mental image: pour water on the starting vertex and watch the terrain flood, lowest ground first. The algorithm repeatedly extracts the vertex with the smallest tentative distance and declares that distance final. The tool is no longer a plain queue but a priority queue — a waiting line that always hands you the smallest item. After finalizing a vertex $u$, for each neighbor $v$ we attempt this update: