How does an automated guided vehicle find its way through a factory hall? Draw obstacles, mark slow zones and watch Dijkstra, A* and Greedy Best-First search for a route from start to goal.
Click & drag to draw · drag the start / goal to move them · after a run, edits update the route live
| Algorithm | Visited | Length | Cost | Time |
|---|---|---|---|---|
| Run all three algorithms on the current layout. | ||||
Moving through a normal cell costs 1, a slow zone (e.g. a pedestrian walkway) costs 5. Movement is 4-directional.
Expands nodes strictly in order of their distance from the start, like a wave. It knows nothing about where the goal is, so it explores in every direction.
optimal routemany visited nodes O((V + E) log V)Dijkstra plus a heuristic: it ranks nodes by f = g + h, the cost so far plus the estimated (Manhattan) distance to the goal. The estimate never overshoots, so the route stays optimal.
optimal routefocused search O((V + E) log V)Only looks at the heuristic and always heads for whatever seems closest to the goal. Very fast, but it ignores what the route has already cost.
few visited nodesnot optimal O((V + E) log V)