Dijkstra's Algorithm
Finds a minimum-cost route for non-negative weights by settling the smallest accumulated cost g(n). Search order follows graph costs, not literal geographic circles.
Minimum weighted cost
O((V + E) log V) time · O(V) space
Interactive learning tool
BayRoute — Pathfinding Lab
See why shortest-path algorithms make different decisions. Step through weighted examples, inspect each expansion, then explore curated road graphs in five regions. The learning view works offline; basemaps are optional.
Browser arcade · keyboard & touch
Maps are context. The graph is the model.
Read the weights, inspect the frontier, and compare the route—not just the animation.
Offline schematic ready.
| Algorithm | Route cost | Settled entries | Compute ms |
|---|
Local landmark search & optional basemaps
Landmark lookup uses the bundled local list only. Supported road regions: the San Francisco Bay Area, New York, Tokyo, London and Taipei. Endpoints snap at most two miles to represented junctions; unsupported or cross-region requests are rejected. No extra roads are created.
External basemaps load only when selected and need network access. Google uses an existing configured or locally stored key if available; this page does not enable services or change billing. Basemap roads are not imported into the search graph, and no live Directions request is made.
Understand the algorithms, step by step
A* Search
Orders the frontier by g(n) + h(n). This implementation scales geographic distance against every represented edge to obtain a consistent lower bound; without useful coordinates h is zero. A heuristic can reduce work, but does not guarantee fewer expansions on every query.
Minimum weighted cost
O((V + E) log V) time · O(V) space
Bidirectional A*
Searches forward and backward on reversed edges using compatible reduced costs. A meeting supplies an upper bound; optimality requires the combined frontier lower bound to reach it. The first meeting alone is not a valid stopping rule.
Minimum weighted cost
O((V + E) log V) time · O(V + E) space
Greedy Best-First
Orders the frontier using only h(n), ignoring the accumulated route cost. It can find a route quickly, but can choose a much more expensive path. With a zero heuristic, ties follow insertion order.
No minimum weighted-cost guarantee
O((V + E) log V) time · O(V) space
Breadth-First Search (BFS)
Traverses the graph layer by layer using a FIFO queue. Minimizes the total number of road segment hops, but ignores speed limits and physical mileage, illustrating why weighted search is essential for navigation.
Minimum hop count, not weighted cost
O(V + E) time · O(V) space
Depth-First Search (DFS)
Follows a branch before backtracking, using a stack and a visited set. It finds a route in a finite reachable graph, but neither minimizes hops nor weighted cost; neighbor order can strongly affect the result.
No minimum weighted-cost guarantee
O(V + E) time · O(V) space
A* uses f(v)=g(v)+h(v). The geometric lower bound is scaled by the smallest edge-cost/geodesic-distance ratio in the graph, making it consistent with every represented directed edge; zero is the safe fallback. Edge weights remain full precision. “Minimum modeled travel time” is not shortest distance or traffic-aware travel time.
Balanced bidirectional A* uses p(v)=(h(v,t)−h(s,v))/2 and reduced edge costs w(u,v)+p(v)−p(u) ≥ 0. The backward search uses reversed adjacency and potential −p. Stop only when the sum of reduced frontier lower bounds reaches the incumbent's reduced route cost. The first common node is not enough.
BFS's g counts hops. Dijkstra/A*'s g counts weighted cost. Non-negative finite weights are required. The race compares recorded work; it is not a benchmark of route planning services.