Graph Database Shortest-Path Query: Bidirectional BFS (2D)

Graph

Nodes 50

Avg. degree (edge density) 3.0

Query Mode

Traversal

Steps / second 5

Live Stats

Nodes visited

Frontier size

Path length (hops)

—

Status

idle

Run a query to compare traversal cost against the other mode on this exact graph.

How it works

A graph database stores each node with direct pointers to its neighbours (index-free adjacency) instead of a foreign-key join table. Answering "shortest path from A to B" means walking those pointers with breadth-first search (BFS), since every hop costs the same and BFS is guaranteed to reach a node via the fewest possible hops.

Single-direction BFS from A:
  visits ≈ O(b^d) nodes, d = distance(A,B), b = avg branching factor

Bidirectional BFS from A and B at once:
  each side only needs to reach depth d/2
  visits ≈ O(2·b^(d/2)) nodes — meets in the middle

This 2D edition runs the identical BFS automaton as the 3D version, but represents it two ways at once, both computed entirely in the plane: a planar spring-electrical graph embedding (left) shows the wavefronts spreading node-to-node exactly like the 3D free embedding, but confined to two dimensions a denser graph visibly tangles its edges in a way the 3D version's extra degree of freedom avoids. Alongside it, a live growth-curve chart (right) plots cumulative nodes visited against BFS layer depth on a log axis — the actual measured curve for the running strategy against the actual measured curve for the untouched other strategy on the very same graph, so the exponential-vs-half-exponential gap from the formulas above is drawn directly from real traversal data, not just illustrated.

Nodes / Avg. degree — regenerate a new random connected graph (a spanning tree plus extra edges) and settle it into a 2D spring-electrical layout.
Bidirectional / Single-Direction — pick which query strategy runs. Source and target are re-chosen as the two farthest-apart nodes reachable in the graph, so the path is never trivial.
Run Query — steps the BFS one graph layer at a time; orange = source-side traversal, cyan = target-side traversal, green = the resolved shortest path.
The growth chart's solid line is the running strategy's real per-layer visited count; the dashed line is the other strategy's real per-layer visited count, computed silently on the same graph for comparison.

Source node Target node Source-side traversal Target-side traversal Shortest path Running strategy (chart) Other strategy, reference (chart)