So the textbook answer to A* versus Dijkstra is that A* wins. It carries a heuristic that points it at the goal, so it expands a narrow cone toward the destination while Dijkstra spreads out in every direction until it trips over it. That is a fine answer. It is the one I would have given you a year ago.
Then I wrote the router for EF-Map, a free 3D map of EVE Frontier, and found that in the mode most people actually use, the A* heuristic is hard-coded to zero. Not tuned down, not scaled. Zero, with a comment above it explaining why. Which means that in that mode A* is not beating Dijkstra at all, it is running a Dijkstra expansion through the A* code path. That took me a while to accept, and I think it is the more useful half of the comparison, so it is what most of this is about.
The graph is not the one you are picturing
Some context first, because the shape of the graph is doing most of the work here. EVE Frontier's universe, as shipped in EF-Map's map database, is 24,026 solar systems spread across 274 regions. There is a stargate network in there, 3,536 bidirectional links, which sounds like plenty until you notice that only 3,033 systems touch a gate at all. The other 20,993 have none. You reach those by pointing your ship at them and jumping, and how far you can jump depends on your hull, your fuel and how hot your drive is running.
So there is no fixed edge list to walk. Most of the edges do not exist until you know whose ship is asking. A neighbour lookup is a geometric question, which systems sit within jump range of this one, and the router answers it with a spatial grid bucketed at roughly the jump distance rather than a precomputed adjacency table. That is already a departure from the classroom version, where somebody hands you the graph and you get on with it.
Two cost functions, and only one of them behaves
You can optimise a route for fuel or for jumps, and the two do very different things.
In fuel mode a stargate edge costs zero. So does a player-built Smart Gate. Gate travel does not burn your own fuel, so the honest cost of taking one is nothing. A ship jump costs its Euclidean length in light years. Optimising for fuel is literally minimising light years travelled under your own drive, with free transit thrown in wherever the network offers it.
In jump mode a gate edge costs exactly 1, a Smart Gate costs 1, and a ship jump costs 1 plus a tiny fraction of the distance, 0.0001 scaled by how much of your range you used. That fraction is a tie-break, so that among routes with the same hop count the shorter one wins, and it is sized small enough that one extra hop always beats any distance penalty.
Why the heuristic has to be zero
A*'s optimality guarantee rests on an admissible heuristic, one that never overestimates the true remaining cost. On a normal spatial graph, straight-line distance is the obvious pick, and it is admissible because you cannot possibly get there for less than the straight line.
Now look at fuel mode again. The quantity being minimised is light years under your own drive, and gate edges cost zero. So the true remaining cost from a system sitting on a gate chain can be zero, while its straight-line distance to the goal is four thousand light years. The heuristic does not just overestimate, it overestimates by everything. And A* with an inadmissible heuristic does not get slower, it gets wrong. It returns a plausible route that is not the best one, and it does it confidently.
There are two ways out and neither is free. Either build a gate-aware heuristic, which means precomputing something about the free network so you can lower-bound the fuel cost properly, or set h to zero and accept that A* degenerates. I set it to zero.
// Mode-aware A* heuristic
// jumps: admissible hop-count lower bound (ceil of Euclidean / maxJumpDistance)
// fuel/explore: h=0 because zero-cost stargate edges break Euclidean admissibility;
// degenerates to Dijkstra-like expansion but keeps the same A* codepath.
const astarH = (a: SolarSystem, b: SolarSystem): number => {
if (optimizeFor === 'jumps') {
if (maxJumpDistance <= 0) return 0;
return Math.ceil(heuristic(a, b) / maxJumpDistance);
}
return 0; // fuel / explore: conservative h=0
};
That is the entire lesson, really. Straight-line distance is only admissible when distance implies cost. The moment some of your edges are free, it stops implying anything, and the standard spatial heuristic everybody reaches for is quietly unsound.
Jump mode does get a real heuristic, because there the cost being minimised is hop count and hop count genuinely has a distance floor. If your maximum jump is 150 light years and the goal is 600 away, you need at least four hops no matter how the gates are laid out. So ceil(euclidean / maxJumpDistance) is an honest lower bound, it is admissible, and it prunes. That is the one mode where the textbook comparison applies on this map.
What the two modes actually produce
The routes themselves make the case better than any of this does. There are twenty route fixtures committed in the repo, real solves against the shipped universe database, asserted on every test run so that a routing change cannot quietly move an answer.
Take OHH-KFD to OQN-R1G, which is 418.5 light years apart in a straight line. Optimised for fuel with an 80 light year range, the answer is 19 hops covering 1,267.2 light years. Optimised for jumps at 150, it is 4 hops covering 538.2. Roughly three times the distance for about a fifth of the hops, same two systems, because fuel mode will happily zigzag across half a region to reach a gate chain that costs nothing to ride.
It gets more extreme the further you go. One of the medium-band cases runs from ACS-D4J to E49-R5M, 5,874.1 light years apart, and the fuel-optimal answer is 178 hops and 14,833.6 light years travelled. That is not the algorithm being clever or stupid. That is what the cost function asked for.
They agree, and I cannot tell you which is faster
Eight of those twenty fixtures are run twice, once with A* and once with bidirectional Dijkstra, same endpoints and same settings. All eight pairs come out identical. Same hop counts, same distances, same reconstructed paths. On the two cases that have no route at all, both also agree on the minimum ship range you would need, 205 light years for one pair and 67.1875 for another. That figure comes from a separate binary search that runs before the solve and stops after seven iterations, which works out at about 0.8 percent precision, so you get told what range would make the trip possible instead of just being told no.
What I do not have is a timing comparison, and I am not going to invent one. An earlier version of this article carried a table of per-route milliseconds and a claim that A* was dramatically faster on long routes. Those figures were fabricated. There is no committed A* versus Dijkstra measurement anywhere in this repository, which is why they are gone rather than corrected. There is a benchmark harness on the map, at ?panel=algo-bench, but it runs on your machine and produces your numbers, and nothing is stored. The only routing timing I can honestly quote is the test suite's own note that the two medium-band fuel routes take about three and a half seconds each.
The h = 0 argument is the stronger claim anyway, and it does not need a stopwatch. In fuel mode A* is performing Dijkstra's expansion plus one extra bookkeeping step per node, so it cannot be meaningfully faster, and the identical routes are the evidence that it really is doing the same search. If you want an actual saving in fuel mode you do not get it from the heuristic. You get it from searching from both ends at once, which is what the Dijkstra path here is, and there is a variant that runs the two frontiers in separate web workers.
I did prototype contraction hierarchies for this at one point, a binary index format, a bidirectional upward search, a Python builder to produce the index. It is still sitting in the repo with nothing importing it. Precomputing a hierarchy is a lovely answer when the graph is fixed, and this graph changes shape with every ship that asks, so I never wired it up. That might be the wrong call. I have not gone back to it.
What I would take from this
If you are choosing between the two for your own project, I do not think the question is which algorithm is faster. It is whether your cost function lets you build an honest lower bound on the remaining cost. If it does, use A*, and everything the textbooks tell you holds. If some of your edges are free, or your cost is measuring something other than distance, check your heuristic against a zero-cost edge before you trust it, because an inadmissible heuristic fails silently. Mine would have.
The reason I say that so plainly is that I did not believe the argument until I had watched it. I set the heuristic to zero, ran the same routes through both solvers, and only when the outputs came back byte for byte identical did the reasoning actually land. Which is a slightly embarrassing thing to admit about a proof that fits in two sentences.
The routing panel on the map lets you pick between A*, the JavaScript bidirectional Dijkstra and the WebAssembly build, so you can run the same route through all of them if you want. In fuel mode I would expect the first two to hand you the same answer. If they ever do not, that is a bug and I would like to hear about it.
Related Posts
Smart Gate Routing: Bidirectional Dijkstra and Gate Directionality is the other half of this, how the bidirectional search handles player-built gates that only work in one direction.
Yeet Planner: Planning EVE Frontier Catapult Routes Before They Go Live is a second solver on the same map, where the edges are catapult shots instead of jumps.
Scout Optimizer: Solving the Traveling Salesman Problem in Space is what happens when you have a pile of waypoints and no fixed order to visit them in.
Jump Calculators: Understanding Your Ship's Heat and Fuel Limits covers where the jump range that feeds all of this actually comes from.
What EF-Map Knows About Every EVE Frontier Solar System is the tour of the underlying database, if you want to know what the 24,026 systems carry.