What you are looking at
Hourglass is an exact point-to-point shortest-path algorithm by Ian Knowles. From version
1.6.2 it is built into Galactus DB as gdb.shortestPath.hourglass. Eight chapters build it
up one idea at a time, then race it against the classics.
- Question. A map of 1,525 places, with roads between neighbours costing 1 to 5. Find the cheapest route from S to T, exactly and with no preprocessing.
- Dijkstra. Settles the nearest place first and floods outwards. It is exact, but it settles everything cheaper to reach than T, in sorted order.
- A*. Adds a guess of the cost still to go. The guess must never overestimate, so on this map it can only lean a little.
- Two funnels. Searches from both ends at once and stops when no route through the meeting point could be cheaper.
- Warp. Hourglass gives every place a potential and re-prices each road with it on doubled costs. Costs stay whole and never negative, both searches lean towards each other, and the answer is still exact.
- Ring. Because re-priced costs are small whole numbers, a ring of buckets replaces the heap. Taking the newest entry first makes equal keys dive along the corridor.
- Race. All four at one operation per tick, on two maps. On the weighted grid Hourglass does the fewest operations. When every road costs 1 the guess is nearly perfect, and A* wins with Hourglass second.
- Galactus DB. Sixteen UK cities, with roads in km and locations as Geography points: Hourglass finds the exact route from Exeter to Newcastle in one call.
Operation counts use the competition harness's rules: queue pushes and pops, edges scanned, distance updates, heuristic evaluations and empty-bucket sweeps.
Things to try
- Pick a chapter from the bar under the scene, or let it run through all eight.
- Warp shows the free roads: every cost-1 road heading towards T costs nothing after re-pricing.
- Race compares the four searches on both heats. The panel under the scene lists the operation counts.