routeplanner

1 Plan a route

A 5×5 road network: local streets at 35 km/h, arterials at 60, a ring motorway at 100. Each edge stores length and speed separately, so shortest and fastest genuinely disagree.

2 Algorithm comparison

Same query, three searches. Expanded / pushed / relaxed are real counters from the runs above — A* expands fewer nodes because its heuristic never overestimates.

3 Why two cost models

Minimising distance and minimising time are different questions. The same pair of intersections can differ by kilometres and half an hour — which is why length and speed are stored on every edge instead of being collapsed into one number at load time.

A* uses great-circle distance to the goal: no road beats the straight line, so the heuristic is admissible and A* returns the same route Dijkstra does — it just looks at less of the map. The travel-time heuristic divides by the fastest speed anywhere in the graph, not the road you are standing on, or a motorway ahead would make it overestimate.

4 Interactive search lab

Drag nodes to reshape the graph, then watch Dijkstra, A* and bidirectional search expand node by node. Nodes are tinted by f(n) = g(n) + h(n) — the priority each algorithm pops from its frontier. Build your own graph with the tools below.

Move mode: drag nodes. Edge mode: click two nodes to connect them (weight = euclidean distance × random factor). Delete: click a node or edge. Double-click an edge to set its weight.

5 Path comparison table

Real numbers from the lab run: distance, estimated travel time, nodes expanded and whether each algorithm found the optimal path.