Graph Traversal

01Why traverse a graph

An NPC decides to walk to the bar, and before it takes a step the engine has to search a map of the level for a route. That search is a graph walk, and a modern engine's frame is a stack of them. A graph here just means things (vertices) joined by links (edges):

• The scene graph links each object to its parent; the engine walks it every frame to compute world transforms. With instancing it becomes a DAG, a directed graph with no cycles.
• The render graph^[1] links rendering passes to the passes whose output they read; those links decide barrier placement, resource lifetimes and async-compute scheduling, and any valid pass order is a topological order, one that puts every dependency first (§8, §15).
• The asset import pipeline links source files and settings to the cooked files built from them; cooking visits it bottom-up so dependencies are baked before dependents.
• The navmesh links walkable polygons to their neighbors, and A* searches it whenever an NPC decides to walk.
• An AI behavior tree is walked depth-first from its root on each tick (event-driven implementations re-walk only the branches an event touched), and animation blend graphs are evaluated inputs-first. Even the shader cache walks each shader's include graph to compute the hash that keys it.

All of that runs on two procedures: breadth-first search (explore outward in rings from the start) and depth-first search (follow one path as far as it goes, then back up). Everything else is a specialization. Dijkstra is BFS with a priority queue. A* is Dijkstra with a heuristic. Topological sort is DFS with a postorder. Tarjan's SCC is DFS with a lowlink trick. Get the two base algorithms right and the rest reduces to "what data structure do I use for the frontier."

The cost of the wrong traversal

The same walk can fit its budget or blow it, depending on how the graph sits in memory. A scene graph with 50,000 entities, traversed once per frame at 60 fps, gives you 333 ns per node if the traversal owns the entire 16.7 ms frame. It never does. Give the scene-graph pass a 1 ms budget (the dashed line in the widget below) and that leaves 20 ns per node to compute the world transform and push it onto the GPU upload buffer. A BFS using std::queue<Entity*> spends little on the queue itself; the cost is a DRAM miss on nearly every entity it dereferences, because the popped pointers arrive in an order that has nothing to do with where the entities sit in memory. One miss costs on the order of 100 ns, five times the per-node budget, before any real work. The same walk over a flat array of entities stored in preorder is a sequential scan: no allocation, no pointer chase, and the hardware prefetcher streams the next entities into cache ahead of the loop. The asymptotic class is the same; the constant factor decides whether the pass fits its budget.

The widget below puts the two on the same axis: entity count along X, microseconds along Y. The "pointer-chase BFS" curve assumes one DRAM-miss-equivalent per node (a hundred-ish nanoseconds on modern hardware, Norvig's ballpark^[4]). The "flat-array DFS" curve starts at one L1 hit per node (about half a nanosecond, from the same table), which is the best case: small nodes, and a prefetcher that keeps up. Nodes that each fill a cache line or more make the scan bandwidth-bound and raise that figure; the third slider sets it. The low end of the pointer-chase slider stands for targets that hit in the L2 or L3 cache instead of DRAM:

02A short history

Why does a shortest-path algorithm published in 1959 still decide how game characters walk? Graph theory predates computing by two centuries (Euler, Seven Bridges of Königsberg, 1736), and graph algorithms arrived with electromechanical switching and didn't slow down.

The engine-relevant line runs from Moore's BFS (1957)^[7] and Dijkstra's shortest paths (1959)^[9], through Kahn's topological sort (1962)^[12] and A* (1968)^[13], to Recast and Detour (2009)^[2] and jump point search (2011)^[20].

03Graphs and how to store them

A navmesh with ten thousand polygons, each touching three neighbors, can take 160 KB or 100 MB depending on how you store it. A graph is a set of vertices and a set of edges between them. Engine-side, vertices are entities, render passes, scene nodes, navmesh polygons; edges are parent-child links, resource dependencies, navmesh adjacencies, behavior-tree transitions. The shape of the graph and what you do with it dictates the storage:

• Directed vs undirected. An edge from u to v may or may not imply an edge from v to u. Scene graph: directed (parent → child). Navmesh adjacency: undirected (you can walk both ways). Render-pass dependency: directed and acyclic.
• Weighted vs unweighted. An edge may carry a cost: distance, time, fuel, an animation blend weight, a navmesh polygon area. Unweighted graphs use BFS to find the shortest path. Weighted graphs need Dijkstra (non-negative weights) or Bellman–Ford (any weights, including negative).
• Sparse vs dense. The classification is the ratio of |E| to |V|². A navmesh is sparse: a polygon has at most one neighbor across each of its edges (a handful per polygon), so |E| = O(|V|). A full complete graph like a "distance from every city to every city" matrix is dense: |E| = Θ(|V|²). The representation you pick has to match.

Three storage layouts cover every case you'll meet:

Adjacency list is the default. Mehlhorn and Sanders^[21] give the full asymptotic comparison; for sparse graphs the matrix wastes space at Θ(|V|²) when most cells are zero, and neighbor enumeration becomes Θ(|V|) per vertex (a full row scan) instead of Θ(deg v). Against a bit-packed matrix, a list with 32-bit neighbor indices breaks even on storage around |E| ≈ |V|² / 32; navmeshes and render graphs sit far below that density.

The cache-friendly adjacency list is not a std::vector<std::vector<int>>. It's two flat arrays in CSR layout: one offsets array and one edges array, both contiguous. Boost.Graph ships it as compressed_sparse_row_graph; SNAP^[22], built for graphs that mutate, instead uses a hash table of nodes with sorted adjacency vectors, trading traversal speed for cheap edits:

// CSR adjacency list. Every traversal on this page runs on this layout.
struct CsrGraph {
    std::vector<int> offsets;   // size |V| + 1
    std::vector<int> edges;     // size |E|
};

// Neighbors of vertex v: contiguous span in 'edges'.
// data() + offset rather than &edges[offset]: a last vertex with no neighbors
// has offsets[v] == edges.size(), and indexing one past the end is UB.
inline std::span<const int> neighbors(const CsrGraph& graph, int v) {
    return { graph.edges.data() + graph.offsets[v],
             static_cast<size_t>(graph.offsets[v + 1] - graph.offsets[v]) };
}

// Vertex count, derived from the offsets array (one entry more than |V|).
inline int vertexCountOf(const CsrGraph& graph) {
    return static_cast<int>(graph.offsets.size()) - 1;
}

Traversal code favors CSR because every neighbor list sits in one contiguous array and the per-vertex index costs 4 bytes. A std::vector<std::vector<int>> spends a 24-byte vector header per vertex (on the common 64-bit standard libraries), so the index alone spans six times as many cache lines, and each neighbor list is a separate heap allocation placed wherever the allocator put it. Beamer's BFS measurements run on graphs stored in CSR^[24], and in the June 2015 Graph 500^[23] rankings he plots, shared-memory machines ran BFS at roughly 10⁸ to 10⁹ traversed edges per second per core.

The widget below shows the same 32-vertex graph stored three ways. Pick a vertex; the representation highlights the work each one does to answer "what are v's neighbors?"

04Breadth-first search

A turn-based tactics game needs every tile a unit can reach in three moves, and the fewest moves to each. BFS visits vertices in increasing order of edge-distance from the source. Level 0 is the source. Level 1 is everything one edge away. Level 2 is everything two edges away that wasn't already on level 1. The data structure that enforces this order is a FIFO queue.

The three-color convention (white = unvisited, gray = in the queue, black = expanded) is the one Cormen, Leiserson, Rivest, and Stein's Introduction to Algorithms^[25] uses for both BFS and DFS, and the one most textbooks now teach. The code below needs only two states (reached or not), because a gray vertex and a black one are handled the same way; the colors make the queue invariant easier to state.

// BFS. Returns parent[] and dist[]. Visits each vertex once, each edge once.
// Complexity: O(|V| + |E|), space O(|V|).
//
// 'parent[v] = -1' for unreached vertices; the source has parent = source.
// 'dist[v]' is the edge-count from source to v.
void bfs(const CsrGraph& graph, int source,
         std::vector<int>& parent,
         std::vector<int>& dist)
{
    const int vertexCount = vertexCountOf(graph);
    parent.assign(vertexCount, -1);
    dist  .assign(vertexCount, -1);

    std::queue<int> frontier;       // gray vertices: in the queue, not yet expanded
    parent[source] = source;        // sentinel: source is its own parent
    dist  [source] = 0;
    frontier.push(source);

    while (!frontier.empty()) {
        int current = frontier.front(); frontier.pop();
        // 'current' transitions from gray to black here.

        for (int neighbor : neighbors(graph, current)) {
            if (parent[neighbor] != -1) continue;   // already gray or black
            parent[neighbor] = current;
            dist  [neighbor] = dist[current] + 1;
            frontier.push(neighbor);                // newly gray
        }
    }
}

A few things are worth pointing out that the textbook usually skims past:

• The check is on discovery, not on expansion. Once a vertex is in the queue, it must not be added again, or the queue grows to O(|E|) entries instead of O(|V|). On dense graphs that can exhaust memory.
• BFS finds the shortest path in edge count, not in weight. Unweighted shortest path is BFS. Weighted shortest path needs Dijkstra (§10). BFS on a weighted graph silently ignores the weights and returns the path with the fewest edges.
• The complexity is O(|V| + |E|). Each reachable vertex is dequeued once and each of its edges is examined once (each undirected edge twice, once from each end), plus the O(|V|) initialization. On a CSR graph the edge reads are runs of contiguous memory, though the order in which runs are visited follows the queue.
• Reconstructing the path is a backward walk through parent from the goal until you hit the source. The path comes out reversed; either build a forward array and std::reverse it, or carry it on a stack as you walk.

The widget below paints a grid with random walls in BFS levels, moving only north, south, east, and west. Level 0 is the source; level k is every cell exactly k moves from it, so the wavefront grows in bands that flow around the walls. Each cell's color and number is its BFS dist[] value:

Bidirectional BFS

If you know both endpoints (source s and goal g) you can launch two BFS frontiers, one from each, and stop when they meet^[15]. The reason this is faster is geometric: on a uniform graph with branching factor b, single-direction BFS explores ~b^d vertices to find a goal at depth d; bidirectional BFS explores ~2b^d/2, about twice the square root of the single-direction count. The catch is implementation discipline: the two searches take turns (strictly alternating, or expanding whichever frontier is smaller), each newly discovered vertex is checked against the other direction's visited set, and the search finishes the current level before stopping, because the first meeting vertex found is not always on a shortest path (§12).

05Depth-first search

Walking a scene graph to update transforms only needs to finish each branch before starting the next, and it should use as little memory as possible doing it. DFS swaps the queue for a stack and otherwise looks identical. The change in data structure changes the order of visits: instead of expanding outward in layers, DFS picks one neighbor, recurses into it, follows that branch as deep as it goes, and only backtracks when there's nothing left to expand. The order of discovery is a preorder traversal of a spanning tree rooted at the source.

DFS comes in two equivalent forms: recursive (uses the call stack as the data structure) and explicit-stack iterative (uses a std::vector as the stack). The recursive form is what algorithm textbooks show. The iterative form is what ships when the graph depth is user-controlled.

// Recursive DFS. Reads cleanly. Crashes on a deep enough graph.
//
// Each recursive call adds one stack frame (~64 bytes on x86-64 with no inlining).
// The default thread stack is 1 MiB on Windows, 8 MiB on Linux. Divide by 64,
// and your scene-graph traversal blows up around 16k to 130k deep.
void dfsRecursive(const CsrGraph& graph, int current,
                  std::vector<int>& visited)
{
    visited[current] = 1;
    for (int neighbor : neighbors(graph, current)) {
        if (visited[neighbor]) continue;
        dfsRecursive(graph, neighbor, visited);
    }
}

// Iterative DFS with an explicit stack. Same preorder as the recursive version,
// no recursion limit. The stack is a heap-allocated std::vector, so its size is
// limited by memory rather than by the thread stack; it can hold up to O(|E|)
// entries, because every expansion pushes all unvisited neighbors and stale
// duplicates wait until they are popped. This is the version that ships.
void dfsIterative(const CsrGraph& graph, int source,
                  std::vector<int>& visited)
{
    std::vector<int> stack;
    stack.push_back(source);

    while (!stack.empty()) {
        int current = stack.back(); stack.pop_back();
        if (visited[current]) continue;     // popped a stale entry
        visited[current] = 1;

        // Push neighbors in reverse so the leftmost neighbor is expanded first.
        // Without this, the order is reversed compared to the recursive version.
        auto adjacent = neighbors(graph, current);
        for (auto neighborIt = adjacent.rbegin(); neighborIt != adjacent.rend(); ++neighborIt) {
            if (!visited[*neighborIt]) stack.push_back(*neighborIt);
        }
    }
}

Both versions are O(|V| + |E|). The iterative version has one wrinkle: by the time you pop a vertex off the stack, it may have been visited by another path that pushed earlier. The if (visited[current]) continue; check guards that case. Forgetting it doesn't break correctness on a tree, but on a general graph with cross edges it visits the same vertex multiple times.

The three colors and edge classification

The three-color version of DFS, marking vertices white (unvisited), gray (on the recursion stack), or black (finished and popped), gives you something BFS doesn't: every edge gets a classification by when its other endpoint changed color^[25]:

• Tree edge. Edge to a white vertex: the edge along which that vertex is discovered. The tree edges of a full DFS form the DFS spanning forest.
• Back edge. Edge to a gray vertex, which is always an ancestor in the DFS tree (or the vertex itself, for a self-loop). A directed graph has a cycle exactly when DFS finds a back edge. This is the textbook cycle detector, and a build system or render-graph compiler can use it to reject a cyclic dependency.
• Forward edge. Edge from a vertex to a black descendant in its own subtree. Only appears in directed graphs.
• Cross edge. Edge from one DFS subtree to a different, already-finished subtree. Only appears in directed graphs.

Maintaining the three colors is a two-line change: set the color to gray on entry to the recursive call and to black on exit. The cost is one extra write per vertex. The colors give cycle detection and topological sort (§8) directly; add discovery indices and a lowlink array and the same skeleton finds strongly connected components (§9), and, on undirected graphs, bridges and articulation points.

06BFS vs DFS, side by side

The shape of the frontier is the visible difference. BFS expands layer by layer; DFS spelunks one branch. Both visit every reachable vertex exactly once. Both are O(|V| + |E|). They give different answers to "what path gets from s to g": BFS returns the path with the fewest edges; DFS returns whichever path its dive happened to follow, often a long one. The widget runs both on the same labyrinth, same source, same goal, one expansion per tick each:

07When to use which

Faced with a new graph problem, the first decision is which walk to use. The decision rule, ordered roughly by how often it comes up:

Two patterns aren't on the table because they're more subtle. Tree problems where sibling order matters (behavior trees, UI hierarchies, the browser's DOM) want DFS preorder: parent, then children left to right. BFS gives layer order, which is almost never what UI or AI wants. Game-state search trees too wide to explore fully (chess, Go, turn-based strategy AI) want neither plain BFS nor plain DFS. They use alpha-beta pruning, a depth-first search that skips provably irrelevant branches, or Monte Carlo Tree Search, a best-first search guided by sampled playouts.

08Topological sort

A DAG always has a linear order on its vertices that respects every edge: every dependency before every dependent. The classic example is a build system: compile util.cpp before main.cpp if main depends on it. The classic engine example is the render graph: the depth pre-pass must finish before the opaque pass that depth-tests against its output. Topological sort produces that order.

Two algorithms exist. Kahn's algorithm (1962^[12]) is the BFS-flavored one: maintain an indegree count for each vertex, push every zero-indegree vertex onto a queue, pop and emit, decrement the indegree of each neighbor, push any neighbor whose indegree just hit zero. The DFS-postorder variant (CLRS chapter 20^[25]; an early description in print is Tarjan's 1976 paper^[34]) runs DFS and emits each vertex when it turns black; the reversed sequence is a topological order.

// Kahn's topological sort. Returns an order respecting every edge,
// or an empty vector if the graph has a cycle.
//
// Complexity: O(|V| + |E|). Each vertex is enqueued once, each edge is
// inspected once when its source is processed.
std::vector<int> topoSortKahn(const CsrGraph& graph) {
    const int vertexCount = vertexCountOf(graph);
    std::vector<int> indegree(vertexCount, 0);

    // First pass: compute every vertex's indegree.
    for (int v = 0; v < vertexCount; ++v)
        for (int neighbor : neighbors(graph, v))
            indegree[neighbor]++;

    std::queue<int> ready;       // vertices with no remaining prerequisites
    for (int v = 0; v < vertexCount; ++v)
        if (indegree[v] == 0) ready.push(v);

    std::vector<int> order;
    order.reserve(vertexCount);

    while (!ready.empty()) {
        int current = ready.front(); ready.pop();
        order.push_back(current);

        for (int neighbor : neighbors(graph, current)) {
            // 'Consume' the edge from current to neighbor: one fewer prerequisite.
            if (--indegree[neighbor] == 0) ready.push(neighbor);
        }
    }

    // Any vertex never emitted is on a cycle or downstream of one.
    if (static_cast<int>(order.size()) != vertexCount) return {};
    return order;
}

Kahn's algorithm detects cycles for free: if the loop exits with vertices still unprocessed, each of them is on a cycle or downstream of one. That leftover set is a superset of the cycle, so an error message built from it names innocent dependents too. To name only the cycle, run an SCC pass (§9) over the leftovers, or use the DFS version: when it finds a back edge u→v, the gray vertices on the recursion stack from v down to u are exactly one cycle, ready to print as "circular dependency: A → B → C → A".

The widget runs Kahn's on a small render graph. Each node shows its indegree counter (how many of its prerequisites haven't been emitted yet); only zero-indegree nodes can be emitted. The order it produces is one valid topological order; there are usually many, and Kahn's picks the one its queue order dictates, which depends on the order of the initial scan:

09Strongly connected components

The asset cooker reports "circular dependency" and stops, and the artist needs to know which files form the loop. A strongly connected component is a maximal set of vertices where every pair can reach each other via directed edges. In a DAG, every SCC is a single vertex (no cycles). In a general directed graph, every cycle lies inside one SCC, and cycles that share a vertex merge into the same SCC; contracting each SCC to a single vertex leaves a DAG. Engine relevance: when a build system, asset cooker, or render graph reports "circular dependency," the useful message is "these SCCs have more than one node, and here are their members." A back edge (§5) proves that a cycle exists; the SCC algorithm lists every vertex caught in one.

Two algorithms ship. Tarjan's (1972^[16]) runs in one DFS pass, maintaining a discovery index per vertex and a "lowlink": the smallest discovery index the vertex's DFS subtree reaches through one edge to a vertex still on the component stack. A vertex whose lowlink equals its own discovery index is the root of an SCC, and it plus everything above it on the stack form the component. Kosaraju–Sharir's (Kosaraju 1978 unpublished; Sharir 1981^[17]) runs two DFS passes: one to get a finish-order on the original graph, a second on the transposed graph in reverse finish-order, where each DFS tree is one SCC. Both are O(|V| + |E|). Tarjan's is faster in practice because it touches the graph once and skips the transpose; Kosaraju's is shorter to write.

// Tarjan's SCC algorithm. One DFS pass, output one component per call to onComponent.
// 'discovery' is the order each vertex was first seen; 'lowlink' is the smallest
// discovery index this vertex's subtree reaches through one edge to a vertex
// that is still on componentStack.
void tarjanScc(const CsrGraph& graph, std::function<void(std::span<const int>)> onComponent) {
    const int vertexCount = vertexCountOf(graph);
    std::vector<int>  discovery(vertexCount, -1);
    std::vector<int>  lowlink  (vertexCount, -1);
    std::vector<bool> onStack   (vertexCount, false);
    std::vector<int>  componentStack;
    int nextIndex = 0;

    auto strongconnect = [&](auto& self, int current) -> void {
        discovery[current] = nextIndex;
        lowlink  [current] = nextIndex;
        nextIndex++;
        componentStack.push_back(current);
        onStack[current] = true;

        for (int neighbor : neighbors(graph, current)) {
            if (discovery[neighbor] == -1) {
                self(self, neighbor);                       // tree edge: recurse
                lowlink[current] = std::min(lowlink[current], lowlink[neighbor]);
            } else if (onStack[neighbor]) {
                // Edge back into an SCC still under construction (a back edge,
                // or a cross edge to a vertex whose component isn't finished).
                lowlink[current] = std::min(lowlink[current], discovery[neighbor]);
            }
            // Else: the neighbor's SCC is already complete and emitted. Skip.
        }

        // If 'current' is the root of an SCC, pop it off the stack.
        if (lowlink[current] == discovery[current]) {
            std::vector<int> component;
            while (true) {
                int popped = componentStack.back();
                componentStack.pop_back();
                onStack[popped] = false;
                component.push_back(popped);
                if (popped == current) break;
            }
            onComponent(component);
        }
    };

    for (int v = 0; v < vertexCount; ++v)
        if (discovery[v] == -1) strongconnect(strongconnect, v);
}

10Shortest paths

BFS already solves the shortest-path problem when every edge costs the same: the first time it pops a vertex, that vertex is as close to the source as it will ever be. Edge weights break that guarantee. Give one edge a cost of 10 while its neighbors cost 1, and BFS, which counts edges and not cost, hands back a two-edge path costing 11 over a four-edge path costing 4. Dijkstra's algorithm is the fix, and A* (§11) is Dijkstra with a heuristic added to the priority.

What Dijkstra does

Dijkstra's algorithm^[9] finds the lowest-cost path from one source to every other vertex, on a graph whose edge weights are all non-negative. It keeps one number per vertex, a tentative distance (0 for the source, ∞ for everything else), and a growing set of settled vertices whose distance is already final. Then it repeats a single move until no unsettled vertex is reachable:

1. Settle the nearest. Take the unsettled vertex with the smallest tentative distance. Its tentative distance is now final: mark it settled.
2. Relax its edges. For each neighbor reached by an edge of weight w, check whether (the settled vertex's distance) + w beats the neighbor's current tentative distance. If it does, lower the neighbor's distance and record the settled vertex as its parent.

That is the entire algorithm. Structurally it is BFS with the frontier changed from a FIFO queue to a min-priority queue keyed on tentative distance. BFS's FIFO queue always returns the vertex that has waited longest, which on a unit-weight graph is exactly the nearest unsettled vertex; keying on accumulated cost instead makes "nearest" mean cheapest-so-far rather than fewest-edges. Relaxing then does one thing BFS never has to: it can lower a vertex's tentative distance after first discovery, because on a weighted graph a cheaper route can surface later. Give every edge weight 1 and that never fires, so the priority queue hands vertices back in the same distance order BFS's FIFO queue does. That coincidence is what "Dijkstra is BFS with a priority queue" means.

Path reconstruction is the same backward walk BFS uses: each relaxation records a parent, and the shortest path to any vertex is its parent chain followed back to the source. With a binary heap for the priority queue the whole search is O((|V| + |E|) log |V|); a Fibonacci heap lowers the bound to O(|E| + |V| log |V|), and bucket or radix queues do better still when edge weights are small integers. In practice the Fibonacci-heap constants are bad enough that a plain binary heap usually wins anyway.

Why settling the nearest vertex is safe

Dijkstra rests on one claim: the moment you settle the unsettled vertex with the smallest tentative distance, that distance is already final. Nothing found later can beat it. Suppose a cheaper path to that vertex did exist. Trace it from the source; it has to leave the settled set somewhere, at some first still-unsettled vertex y. The cost to reach y along that path is at least y's own tentative distance, because the settled vertex just before y relaxed its edge to y when it was settled; y is unsettled, so its tentative distance is at least the one you are about to settle; and every edge past y adds a non-negative amount. The supposedly cheaper path therefore costs at least as much, which contradicts the assumption.^[25] That single step is where the non-negative-weight requirement lives: one negative edge past y could drag the total back down, the guarantee fails, and you need Bellman–Ford instead (covered below, and flagged again in §16).

The widget runs Dijkstra on terrain with cost, moving only north, south, east, and west. Plain dark cells are cheap (entering one costs 1); the amber-hatched columns are slow (entering one costs 8), and each column has a short cheap gap. It settles one vertex per tick, tints each by its final cost from the source, and labels that cost when the cells are large enough to hold a number. The wavefront is a cost contour, not the even ring BFS painted in §4: it surges through cheap ground and lags against the slow bands, because a longer detour over cheap cells outranks a short hop through expensive ones.

// Weighted CSR: the CsrGraph from §3 plus a per-edge weight array parallel
// to 'edges', so weights[i] is the cost of the edge stored at edges[i].
struct WeightedCsr {
    std::vector<int>    offsets;   // size |V| + 1
    std::vector<int>    edges;     // size |E|
    std::vector<double> weights;   // size |E|
};

// (neighbor, weight) pairs for vertex v. Allocates for exposition; hot-path
// code iterates the edge and weight spans directly instead.
inline std::vector<std::pair<int, double>> weightedNeighbors(const WeightedCsr& graph, int v) {
    std::vector<std::pair<int, double>> result;
    for (int e = graph.offsets[v]; e < graph.offsets[v + 1]; ++e)
        result.emplace_back(graph.edges[e], graph.weights[e]);
    return result;
}

// Dijkstra's algorithm with a binary heap.
// Returns a dist[] array; dist[v] = shortest cost from source to v, or +inf.
//
// Complexity: O((|V| + |E|) log |V|). With lazy deletion (below) a vertex is
// pushed once per successful relaxation, at most once per incoming edge, so the
// heap sees up to |E| + 1 insertions; log |E| <= 2 log |V|, so the bound holds.
// For dense graphs, an O(|V|^2) array scan in place of the heap is faster.
void dijkstra(const WeightedCsr& graph, int source,
              std::vector<double>& dist,
              std::vector<int>&    parent)
{
    const int vertexCount = static_cast<int>(graph.offsets.size()) - 1;
    dist  .assign(vertexCount, std::numeric_limits<double>::infinity());
    parent.assign(vertexCount, -1);

    using Entry = std::pair<double, int>;             // (cost, vertex)
    std::priority_queue<Entry, std::vector<Entry>, std::greater<Entry>> frontier;

    dist[source] = 0.0;
    frontier.emplace(0.0, source);

    while (!frontier.empty()) {
        auto [cost, current] = frontier.top(); frontier.pop();
        if (cost > dist[current]) continue;            // stale entry, skip

        for (auto [neighbor, weight] : weightedNeighbors(graph, current)) {
            double newCost = cost + weight;
            if (newCost < dist[neighbor]) {
                dist  [neighbor] = newCost;
                parent[neighbor] = current;
                frontier.emplace(newCost, neighbor);   // lazy: leave stale entries
            }
        }
    }
}

Three implementation details to get right or you'll have a slow or wrong Dijkstra:

• Lazy deletion. When a vertex's distance improves, the old entry stays in the heap. The if (cost > dist[current]) continue; skips it on pop. The alternative, finding and removing the old entry, needs a heap that supports decrease-key, which std::priority_queue doesn't.
• Negative weights kill correctness. Dijkstra's invariant ("the first time v is popped, dist[v] is final") relies on edges being non-negative. A negative edge can lower a "finished" vertex's distance after the fact. If your weights are sometimes negative, use Bellman–Ford.
• Floating-point ties. When two routes cost the same or nearly the same, heap order decides which one wins. On a grid with diagonal moves or a navmesh with floating-point edge lengths, a tiny change in the start position can flip the chosen route from one frame to the next, and the agent visibly dithers. Round costs to a stable precision, break exact ties on a deterministic secondary key (vertex id), or keep following the current path until a new one is cheaper by a margin.

The rest of the shortest-path family

Dijkstra is the default, but it is one member of a family. The others either restrict the weights to run faster (BFS, 0-1 BFS) or widen the problem to cases Dijkstra can't handle (negative weights, every pair of vertices):

• BFS is Dijkstra for unit weights, at O(|V| + |E|) with a plain FIFO queue instead of a heap. When every edge costs the same, the heap is wasted overhead.
• 0-1 BFS handles edge weights that are only 0 or 1. Use a std::deque: push 0-weight neighbors to the front, 1-weight neighbors to the back. Still O(|V| + |E|), no heap needed.
• Bellman–Ford (Bellman 1958^[8], Ford 1956^[6], Moore 1959^[7]) is the one to reach for when weights can be negative. Relax every edge |V|−1 times. O(|V| · |E|) worst case, and it detects negative cycles for free: if any edge still relaxes on the |V|th pass, a negative cycle is reachable from the source.
• Floyd–Warshall computes shortest paths between every pair of vertices in O(|V|³) time and O(|V|²) memory. For a small dense graph (a 16×16 cost table between AI tactical regions) it's the right tool; for a navmesh with 10,000 polys it's 10¹² steps and a 100-million-entry table.

11A* and admissible heuristics

Dijkstra searches in every direction equally, so an NPC crossing a large map expands cells behind it as eagerly as cells toward its goal. A* is Dijkstra with one change: the priority isn't g(v) (cost from source) but g(v) + h(v), where h(v) is an estimate of the cost from v to the goal^[13]. The estimate biases expansion toward the goal: vertices that look close get popped first. If the heuristic is good, A* expands a small fraction of the vertices Dijkstra would. If the heuristic is h(v) = 0, A* is exactly Dijkstra.

Heuristic best-first search already existed (the Graph Traverser program, which Nilsson first considered for Shakey, ordered its frontier by the estimate h alone); the 1968 paper added the cost-so-far term g to the priority and proved when the result is optimal:

The consistency condition decides what an implementation has to do with closed vertices (ones already expanded). With a consistent heuristic, a closed vertex can be skipped forever, which is what the widget below does. With a heuristic that is admissible but not consistent, A* can later find a cheaper path to a closed vertex; to keep the optimality guarantee it must reopen that vertex and expand it again. Detour's findPath reopens closed polygons whenever a cheaper route turns up^[31].

On a 2D grid, the canonical admissible heuristics are:

• Manhattan distance |Δx| + |Δy|: admissible for 4-connected grids (only N/S/E/W moves).
• Octile distance max(|Δx|, |Δy|) + (√2−1) · min(|Δx|, |Δy|): admissible for 8-connected grids with diagonal cost √2.
• Euclidean distance √(Δx² + Δy²): admissible for any grid; loose for the 4- and 8-connected cases. Use only when the grid allows arbitrary-angle moves (rare in tiles, common on navmesh).

On a navmesh, the usual heuristic is straight-line distance from the search node to the goal. No path between two points is shorter than the straight line, so it is admissible as long as no area costs less than 1 per unit of distance. Detour places each search node at the midpoint of the polygon edge it was entered through, charges distance times the area's cost, and scales the straight-line heuristic by 0.999, just under 1^[31]. Multiply the heuristic by a constant w > 1 (weighted A*) and A* usually expands fewer nodes, but it gives up the optimality guarantee: with an admissible h, the path it returns costs at most w times the optimum. It is a common speed/quality knob in game pathfinding^[26].

The widget runs Dijkstra and A* side by side on the same 8-connected grid (straight moves cost 1, diagonals √2) with the same source and goal, using the octile heuristic. The heuristic-weight slider goes from 0 (= Dijkstra) past 1 (admissible) to 2.5 (greedy and possibly suboptimal). "Run" replays both searches one expansion per tick; moving the slider shows the finished result immediately:

12Bidirectional search

A path query between two points far apart explores a huge region around the start before it gets near the goal. Pohl's observation^[15]: if a uniform-branching graph has branching factor b and the goal is at depth d, a single-direction BFS explores ~b^d vertices to find it. Two BFS frontiers (one from the source, one from the goal, alternating expansion) meet in the middle after expanding ~2 · b^d/2. The branching factor still applies, but the exponent halves. On a graph with b = 10 and d = 12, the single-direction count is 10¹²; the bidirectional count is 2 · 10⁶. That gain does not carry over automatically to bidirectional A*. A good heuristic already keeps a one-way search narrow, and for decades bidirectional heuristic search did worse than plain A* in practice; Kaindl and Kainz showed that the popular explanation, frontiers passing each other without meeting, was wrong, and gave bidirectional variants that beat one-way search on some hard problems^[33].

The catch is termination. The frontiers must exchange visited sets, and the meeting point isn't necessarily the first vertex one search reaches that the other has already seen; the shortest path runs through the vertex that minimizes dist_fwd(v) + dist_back(v). Keep the best such sum found so far and stop only when the two frontiers' smallest keys prove nothing cheaper can still appear (for bidirectional Dijkstra, when the two minimum queue keys add up to at least that best sum). Stop at the first meeting and the path you return can be longer than the shortest one.

13JPS and hierarchical pathfinding

An RTS map 1,000 cells on a side has a million cells, and a few hundred units asking for paths every second. Plain A* expands more nodes as maps grow; two optimizations cut that count on large grid maps:

Jump Point Search (Harabor & Grastien, AAAI 2011^[20]) exploits a symmetry property of uniform-cost 8-connected grids: many paths through open space are interchangeable. JPS prunes the search by skipping intermediate cells that no optimal path needs to expand, jumping directly to "jump points": cells next to an obstacle corner where an optimal path may turn, and the goal. The paper reports speedups over A* from about 2× on short paths to about 30× on long ones, on HOG2 maps from Baldur's Gate II and Dragon Age: Origins plus two synthetic sets. JPS is restricted to uniform-cost grids (variable terrain cost breaks its symmetry argument), but for tile-based maps where every cell is either walkable or blocked it is a common choice.

Hierarchical Pathfinding A* (HPA*, Botea, Müller, Schaeffer, 2004^[19]) partitions the map into clusters at one or more abstraction levels. At build time, it places entrance nodes on the borders between neighboring clusters and, inside each cluster, computes the shortest path between every pair of that cluster's entrance nodes; those costs become the edges of a small "abstract graph". At query time it inserts the source and goal into the abstract graph, runs A* there, then refines each abstract edge into a real path. The Botea paper reports up to 10× faster searches than a highly optimized A*, with paths within 1% of optimal after smoothing. Later hierarchical schemes, such as Sturtevant and Buro's partial-refinement A* (PRA*), tune the same trade.

14Iterative deepening

A puzzle solver searching move sequences runs out of memory long before it runs out of time, because BFS keeps the whole frontier. BFS finds the shortest path but uses memory proportional to the frontier; for a uniform tree with branching b and goal at depth d, that's O(b^d). DFS on a tree uses memory proportional to depth (O(d) for the recursive form) but doesn't find shortest paths.

Iterative-deepening DFS (Korf 1985^[18]) gets both. Run depth-limited DFS with limit 1; if not found, throw it away and run again with limit 2; then 3; and so on. The repeated work looks wasteful but isn't: on a uniformly branching tree, the last iteration does most of the work (b^d nodes), and all earlier iterations combined do less (the geometric sum is b^d/(b−1)). For b = 10 the overhead is about 11%.

IDA* in the same Korf paper combines this with A*'s heuristic: at each iteration, the cutoff is on f(v) = g(v) + h(v), not depth. IDA* is a standard choice in classical-AI puzzle solving when the state space is too large for A*'s open set to fit in memory (sliding-tile puzzles, Rubik's cube, Sokoban). For game-engine navigation it's almost never the right choice: the navmesh fits in memory, and IDA* re-expands the same vertices on every iteration. Plain iterative deepening does ship in game AI, as the driver for alpha-beta search in board-game engines: searching depth 1, then 2, then 3 leaves a best move ready whenever the time budget runs out.

15Case studies

Five places in shipping engines where these walks run every frame or every build.

1 · The render-graph compile

Render-graph systems (Frostbite's FrameGraph^[27], Unreal's RDG, the RenderGraph in Unity's Scriptable Render Pipeline) record each frame's rendering work as passes that declare the resources they read and write, then compile that record before executing it. O'Donnell's Frostbite talk splits compilation into culling and resource allocation, and both are graph walks, as is choosing the order:

1. Culling drops every pass whose outputs nothing reads, directly or through later passes: reachability computed backwards from the frame's real outputs. Frostbite implements it as a reference-count flood fill. Every resource starts with a count of its readers and every pass with a count of the resources it writes; resources with no readers go on a stack, and popping one decrements its producer's count. A producer that reaches zero is culled, which in turn decrements the counts of the resources it reads.
2. Resource lifetimes come from one walk over the surviving passes in execution order, recording each transient resource's first and last user. Frostbite acquires memory right before the first use and releases it after the last, so two render targets whose lifetimes don't overlap can share the same physical allocation.
3. Ordering must respect every read-after-write dependency, which makes it a topological sort (§8). When a pass can only read resources that earlier-declared passes produced, the declaration order already is one. Render graphs that reorder passes to overlap GPU work sort explicitly: Granite's walks back from the backbuffer recursively, pushing every pass that writes a resource an already-listed pass reads, then reverses the list and prunes duplicates^[35].

A graph built so that passes only read what earlier passes produced cannot express a cycle. One assembled from arbitrary dependency edges needs the back-edge check from §5 to reject one.

2 · F.E.A.R.'s planner: A* over actions

F.E.A.R. (Monolith, 2005) shipped a GOAP planner in place of a large hand-authored state machine; its character state machine has only three states. Jeff Orkin's GDC 2006 paper^[3] describes the system: each NPC has an Action Set, actions carry preconditions, effects, and a cost, and the AI runs A* over a graph whose nodes are world states and whose edges are actions, searching for the lowest-cost action sequence that satisfies the current goal. The same A* code also plans paths through the navmesh. Action Sets are authored per character type: given the same goals, the soldier patrols and opens fire, the assassin runs cloaked, clings to walls, and lunges into melee, and the rat only patrols because it has no attack actions. When an action fails, the character replans with what it learned; in the paper's example, a character whose door the player holds shut tries to open it, replans to kick it, and replans again to dive through a window. The state graph is implicit; A* generates it as it expands.

3 · Asset cooking and the SCC report

An engine's asset cooker walks a dependency DAG: a character references a skeletal mesh and an animation graph, both reference a skeleton, the mesh references its materials, and each material references shaders and textures. Cooking visits the DAG bottom-up (reverse topological order: each dependency is baked before each dependent). When a content author accidentally introduces a cycle (say, a material and a material function that reference each other), an SCC pass (§9) turns the failure into a report naming the members: every SCC with more than one vertex is a cycle group, and Tarjan's algorithm emits each group as one pop sequence off its stack. Printing an ordered loop such as "circular dependency: M_RustyBarrel → MF_RustNoise → M_RustyBarrel" then takes one short DFS inside the component.

4 · Scene-graph traversal: flat preorder beats recursive

The fast scene-graph layout stores the hierarchy in a flat array ordered so every parent comes before its children: preorder, or breadth-first (level) order, which also keeps siblings contiguous. Each entry holds its parent's index. Computing world transforms is a single sequential pass over the array: each entity's world transform is its local transform composed with its parent's world transform, and the parent has already been processed because of the ordering. The pass needs no queue, no stack, and no pointer chase. The asymptotic class is the same as recursive DFS; the constant factor drops because the per-node DRAM miss is gone. Unity's Entities package takes the ECS route to the same data: transforms are plain components (LocalTransform in, LocalToWorld out), and a dedicated system recomputes LocalToWorld from the hierarchy each update^[28].

5 · Navmesh A* in CryEngine, Unreal, and Detour

CryEngine documents its pathfinder as A* over the triangles of its navigation mesh, with the distance to the destination as the heuristic, time-sliced so path requests queue up and complete over several frames instead of spiking one^[29]. Unreal's navmesh is a RecastNavMesh actor^[30], and Recast's README lists both Unreal and Unity among the engines it powers^[2]. Detour's own findPath is a compact A* worth reading: node positions at portal-edge midpoints, costs as distance times area cost, the 0.999-scaled straight-line heuristic, and closed nodes reopened when a cheaper route turns up^[31].

16Pitfalls

Bugs that recur in graph-traversal code:

• Marking visited on expand instead of on discovery. The BFS bug: if you mark a vertex as visited when you pop it instead of when you push it, the same vertex can be pushed multiple times by different neighbors. The queue grows to O(|E|) entries instead of O(|V|), and on dense graphs that can exhaust memory.
• Recursive DFS on user content. Already covered in §5. The fix is the iterative form. If you keep the recursive form, set an explicit depth limit and fail loudly when it's exceeded.
• BFS on a weighted graph. BFS returns the path with the fewest edges, not the fewest weight units. If your edges have weights and you care about cost, use Dijkstra. In a game it shows up as an NPC taking the long, slow road because it has fewer waypoints.
• Dijkstra with negative weights. Dijkstra's correctness depends on the invariant that once a vertex is popped, its distance is final. A negative edge can update a finalized vertex, and Dijkstra never reconsiders it. Use Bellman–Ford if your weights are sometimes negative.
• A* with an inadmissible heuristic. If h(v) > h*(v) for some v, A* can return a suboptimal path. Often deliberate (weighted A* is faster), but should be explicit, not an oversight in the heuristic.
• Floating-point ties in shortest-path. Equal-cost paths are chosen by heap order, which shifts when the graph is edited or the neighbor order changes, and float rounding can differ across compilers and platforms. Break ties on a deterministic secondary key (lowest vertex id), or round costs to a stable precision.
• SCC report says "no cycle" but the build fails with a circular dependency. The graph the SCC pass runs on and the one the build system executes can disagree, for example when one is captured before a code-generation step and the other after. The SCC algorithm is correct; check that you're feeding it the post-codegen graph.
• Topological order isn't unique. Kahn's output depends on queue order, which depends on the initial scan order, which depends on how vertices were numbered. If you rely on a specific order (for reproducible builds, for the order in which render passes execute), replace the FIFO with a priority queue keyed on a stable id such as the asset path.
• Adjacency-list reallocation invalidating iterators mid-traversal. Calling graph.addEdge(...) while a BFS is in progress and the underlying std::vector<int> reallocates leaves the BFS iterating into freed memory. Either snapshot the graph, or queue the edits and apply them after the traversal finishes.

17What's next

In this series the next page is Behavior Trees, the depth-first-walked tree that decides what an NPC does once it can find its way. Beyond this page, the graph algorithms worth knowing next:

• Best-first search beyond A*. D* (Stentz 1994) and D* Lite (Koenig and Likhachev 2002) repair a path incrementally when the graph changes instead of searching from scratch; Theta* (Daniel et al. 2010) finds any-angle paths on grids; SMA* (Russell 1992) searches within a fixed memory budget.
• Min-cost flow and max flow. Edmonds–Karp (BFS-based augmenting paths), Dinic, push-relabel. The graph-algorithm family that handles allocation problems: bandwidth, scheduling, network reliability.
• Minimum spanning trees. Kruskal (sort edges, union-find), Prim (grow one tree from a priority queue keyed on edge weight). Dijkstra's 1959 paper gives a Prim-style MST algorithm alongside the shortest path; both are in the same three-page note.
• Graph partitioning and clustering. METIS, KaHIP. For HPA*-style hierarchical pathfinding, scene-graph load balancing across worker threads, and asset-bundle planning.
• Parallel and GPU graph algorithms. Direction-optimizing BFS (Beamer et al. 2012; the thesis^[24] covers it), which switches to having each unvisited vertex look for a parent in the current frontier when the frontier is large; GPU frameworks such as Gunrock and cuGraph. The same ideas apply when thousands of units share one flow field or distance map.
• Persistent data structures. Building a graph traversal that snapshots its visited set at each step for time-travel debugging. Debugging in release covers the broader topic.

For an engine programmer, a practical next step is to read two real implementations: your engine's render-graph compile step (culling, lifetime computation, and ordering, as in §15) and Detour's dtNavMeshQuery::findPath. Both are short, and both are built from the traversals on this page.

Sources

1. Yuriy O'Donnell. "FrameGraph: Extensible Rendering Architecture in Frostbite." Game Developers Conference 2017. gdcvault.com/play/1024612. The widely cited engineering talk on render-graph compilation: the setup, compile, and execute phases, culling of unreferenced passes and resources, and transient-resource lifetimes and aliasing, as described in §15.
2. Mikko Mononen et al. "Recast Navigation." GitHub repository (zlib license), originally released 2009. github.com/recastnavigation/recastnavigation. The README states that Recast "powers AI navigation features in Unity, Unreal, Godot, O3DE and countless AAA and indie games and engines"; the project's introduction page credits Mononen as the original author, in 2009, and the license file carries his 2009 copyright.
3. Jeff Orkin. "Three states and a plan: The A.I. of F.E.A.R." Game Developers Conference 2006. gamedevs.org/uploads/three-states-plan-ai-of-fear.pdf. The source for F.E.A.R.'s GOAP system: the character FSM is reduced to three states (Goto, Animate, Use Smart Object), A* plans action sequences as well as navmesh paths, and the soldier, assassin, and rat examples of per-character Action Sets.
4. Peter Norvig. "Teach Yourself Programming in Ten Years," "Approximate timing for various operations" table. norvig.com/21-days.html. Memory-hierarchy latency ballparks used to estimate per-node traversal cost: L1 ~0.5 ns, branch mispredict ~5 ns, DRAM ~100 ns.
5. Édouard Lucas. Récréations mathématiques, Vol. I, 2nd ed., Paris: Gauthier-Villars, 1882. Chapter 3, "Le jeu des labyrinthes," attributes the maze procedure (depth-first search with passage marking) to Trémaux, "a former student of the École Polytechnique" and telegraph engineer. archive.org hosts a public-domain scan of an 1891 printing of Vol. I (New York Public Library copy).
6. Lester R. Ford, Jr. Network Flow Theory. Paper P-923, The RAND Corporation, August 14, 1956. rand.org/pubs/papers/P923. The relaxation-style shortest-path procedure that, with Bellman 1958 and Moore 1959, is the joint origin of Bellman–Ford.
7. Edward F. Moore. "The shortest path through a maze." In Proceedings of the International Symposium on the Theory of Switching, Part II, April 2–5, 1957, Annals of the Computation Laboratory of Harvard University, Vol. 30, pp. 285–292. Harvard University Press, 1959. Algorithm A is usually credited as the first published BFS; Schrijver's history of the shortest-path problem (Documenta Mathematica, Extra Volume ISMP, 2012, pp. 155–167) summarizes the paper and its motivation, routing toll telephone traffic.
8. Richard Bellman. "On a Routing Problem." Quarterly of Applied Mathematics 16(1):87–90, 1958. DOI: 10.1090/qam/102435. ams.org/journals/qam/1958-16-01. The dynamic-programming functional equation for shortest paths.
9. Edsger W. Dijkstra. "A note on two problems in connexion with graphs." Numerische Mathematik 1(1):269–271, 1959. DOI: 10.1007/BF01386390. link.springer.com/article/10.1007/BF01386390. Three pages, two algorithms: shortest path between two given vertices, and minimum spanning tree.
10. Thomas J. Misa, Philip L. Frana. "An Interview with Edsger W. Dijkstra." Communications of the ACM 53(8):41–47, August 2010. cacm.acm.org/research/an-interview-with-edsger-w-dijkstra. Dijkstra's own account of designing the shortest-path algorithm in about twenty minutes in a 1956 Amsterdam café "without pencil and paper."
11. C. Y. Lee. "An algorithm for path connections and its applications." IRE Transactions on Electronic Computers EC-10(3):346–365, 1961. DOI: 10.1109/TEC.1961.5219222. BFS independently re-derived for circuit routing; the "Lee algorithm" of EDA textbooks.
12. Arthur B. Kahn. "Topological sorting of large networks." Communications of the ACM 5(11):558–562, November 1962. DOI: 10.1145/368996.369025. dl.acm.org/doi/10.1145/368996.369025. The indegree-queue algorithm. The abstract reports ordering a 30,000-activity PERT network in under an hour on an IBM 7090, and describes the method as a by-product of a procedure needed by Westinghouse, Baltimore.
13. Peter E. Hart, Nils J. Nilsson, Bertram Raphael. "A Formal Basis for the Heuristic Determination of Minimum Cost Paths." IEEE Transactions on Systems Science and Cybernetics SSC-4(2):100–107, 1968. DOI: 10.1109/TSSC.1968.300136. ieeexplore.ieee.org/document/4082128. The A* paper; introduces the algorithm and proves the admissibility theorem.
14. Peter E. Hart, Nils J. Nilsson, Bertram Raphael. "Correction to 'A formal basis for the heuristic determination of minimum cost paths'." SIGART Newsletter 37:28–29, 1972. DOI: 10.1145/1056777.1056779. dl.acm.org/doi/10.1145/1056777.1056779. The short correction that claimed the optimal-efficiency theorem holds without the consistency assumption; Dechter and Pearl [32] later showed that claim false.
15. Ira Pohl. Bi-directional and heuristic search in path problems. Ph.D. dissertation, Stanford University, May 1969. Also issued as SLAC report SLAC-104. slac.stanford.edu/pubs/slacreports/reports04/slac-r-104.pdf. The original framing of bidirectional heuristic search; the conventionally cited "Pohl 1971" is the Machine Intelligence 6 chapter that followed.
16. Robert Tarjan. "Depth-first search and linear graph algorithms." SIAM Journal on Computing 1(2):146–160, 1972. DOI: 10.1137/0201010. epubs.siam.org/doi/10.1137/0201010. The paper that formalizes DFS as a general technique and gives the linear-time SCC and biconnected-components algorithms.
17. Micha Sharir. "A strong-connectivity algorithm and its applications in data flow analysis." Computers & Mathematics with Applications 7(1):67–72, 1981. DOI: 10.1016/0898-1221(81)90008-0. sciencedirect.com/science/article/pii/0898122181900080. The two-pass SCC algorithm. S. Rao Kosaraju described the same algorithm in unpublished work in 1978, and Aho, Hopcroft, and Ullman's Data Structures and Algorithms (1983) credits both authors, hence "Kosaraju–Sharir."
18. Richard E. Korf. "Depth-first iterative-deepening: An optimal admissible tree search." Artificial Intelligence 27(1):97–109, 1985. DOI: 10.1016/0004-3702(85)90084-0. sciencedirect.com/science/article/abs/pii/0004370285900840. The IDDFS paper; also introduces IDA*.
19. Adi Botea, Martin Müller, Jonathan Schaeffer. "Near optimal hierarchical path-finding." Journal of Game Development 1(1):7–28, 2004. webdocs.cs.ualberta.ca/~mmueller/ps/2004/hpastar.pdf. The HPA* paper; reports up to 10× speedup over a highly optimized A*, with paths within 1% of optimal.
20. Daniel Harabor, Alban Grastien. "Online graph pruning for pathfinding on grid maps." In Proc. AAAI Conference on Artificial Intelligence (AAAI-11), pp. 1114–1119, 2011. ojs.aaai.org/index.php/AAAI/article/view/7994. The Jump Point Search paper; symmetry pruning on uniform-cost grids. The abstract reports that jump points "can speed up A* by an order of magnitude and more"; per-benchmark speedups on the HOG2 map sets run from about 2× to about 30×, growing with path length (summarized on the first author's blog, harablog.wordpress.com).
21. Kurt Mehlhorn, Peter Sanders. Algorithms and Data Structures: The Basic Toolbox. Springer, 2008, chapter 8 "Graph Representation." people.mpi-inf.mpg.de/~mehlhorn/ftp/NewToolbox/grepresent.pdf. The asymptotic comparison of adjacency list, adjacency matrix, and edge list representations.
22. Jure Leskovec, Rok Sosič. "SNAP: A general-purpose network analysis and graph-mining library." ACM Transactions on Intelligent Systems and Technology 8(1):1:1–1:20, 2016. DOI: 10.1145/2898361. snap.stanford.edu/snap. Stanford's network-analysis library; the paper describes its storage as a hash table of nodes with sorted adjacency vectors, the mutable-graph alternative to CSR discussed in §3.
23. Graph500 Steering Committee. "Graph500 benchmark specification." graph500.org/?page_id=12. The reference BFS benchmark spec used in the parallel-graph-algorithms literature; defines scale-S as a Kronecker graph with 2^S vertices.
24. Scott Beamer. Understanding and Improving Graph Algorithm Performance. Ph.D. thesis, UC Berkeley, 2016. escholarship.org/uc/item/4jp775f7. Also issued as UC Berkeley tech report EECS-2016-153. Direction-optimizing BFS, the GAP benchmark suite, and BFS measurements on graphs stored in CSR ("We operate on graphs stored in memory in Compressed Sparse Row (CSR) format"); its Figure 1.1 plots per-core BFS rates for the June 2015 Graph 500 rankings, with shared-memory systems at roughly 10⁸–10⁹ traversed edges per second per core.
25. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Introduction to Algorithms, 4th ed. MIT Press, 2022. ISBN 9780262046305. mitpress.mit.edu/9780262046305. Chapter 20 covers BFS, DFS (with the white/gray/black coloring), topological sort, and SCC. Chapters 22–23 cover shortest paths, including the correctness proof of Dijkstra's algorithm.
26. Amit Patel. "Introduction to A*." Red Blob Games, ongoing. redblobgames.com/pathfinding/a-star/introduction.html. Interactive explanation of BFS, Dijkstra, and A*, including weighted A* and heuristic scaling; the companion implementation guide covers tie-breaking and priority-queue details.
27. Yuriy O'Donnell. "FrameGraph: Extensible Rendering Architecture in Frostbite." GDC 2017. Same talk as [1]; slides on SlideShare. The compile-phase slides describe culling unreferenced passes and resources with a reference-count flood fill and computing transient-resource lifetimes ("acquire right before first use, release after last use"), as summarized in §15.
28. Unity Technologies. "Transforms concepts." Unity Entities 1.0 documentation. docs.unity3d.com/Packages/com.unity.entities@1.0/manual/transforms-concepts.html. Describes LocalTransform, LocalToWorld, the Parent/Child components, and the LocalToWorldSystem that recomputes world transforms from the hierarchy.
29. Crytek. "Navmesh Pathfinding." CRYENGINE V Manual. cryengine.com/docs/static/engines/cryengine-5/…/pages/25534842. "The pathfinder uses the A* search on the triangles of the mesh, with the distance to the destination as the heuristic"; also documents the time-sliced request queue.
30. Epic Games. "Basic Navigation in Unreal Engine." Unreal Engine documentation. dev.epicgames.com/documentation/en-us/unreal-engine/basic-navigation-in-unreal-engine. The navmesh a level generates is the RecastNavMesh-Default actor.
31. Recast Navigation contributors. DetourNavMeshQuery.cpp, dtNavMeshQuery::findPath. github.com/recastnavigation/recastnavigation/…/DetourNavMeshQuery.cpp. Detour's polygon A*: search nodes at portal-edge midpoints, cost as distance times area cost, heuristic as straight-line distance times H_SCALE = 0.999f, and closed nodes reopened when a cheaper total is found.
32. Rina Dechter, Judea Pearl. "Generalized best-first search strategies and the optimality of A*." Journal of the ACM 32(3):505–536, 1985. DOI: 10.1145/3828.3830. dl.acm.org/doi/10.1145/3828.3830. The definitive study of A*'s optimal efficiency; shows the consistency assumption cannot be dropped, contrary to the 1972 correction.
33. Hermann Kaindl, Gerhard Kainz. "Bidirectional Heuristic Search Reconsidered." Journal of Artificial Intelligence Research 7:283–317, 1997. DOI: 10.1613/jair.460. jair.org/index.php/jair/article/view/10199. Shows the "frontiers pass each other" explanation for bidirectional heuristic search's poor results is wrong, and reports variants that beat unidirectional search on some difficult problems.
34. Robert Endre Tarjan. "Edge-disjoint spanning trees and depth-first search." Acta Informatica 6(2):171–185, 1976. DOI: 10.1007/BF00268499. link.springer.com/article/10.1007/BF00268499. An early printed description of topological sorting by depth-first search.
35. Hans-Kristian Arntzen (Themaister). "Render graphs and Vulkan — a deep dive." Blog post, August 2017. themaister.net/blog/2017/08/15/render-graphs-and-vulkan-a-deep-dive. Describes the Granite renderer's graph compile, including the recursive walk back from the backbuffer, list reversal, and duplicate pruning that produce its pass order before reordering.