Wegfindungs-Algorithmen
Dijkstra's algorithm and A* both find shortest paths, but they explore very differently. This visualiser draws the search as it happens so you can see A* driving straight at the goal while Dijkstra spreads out in all directions.
So benutzt du diese Simulation
- Choose between A*, Dijkstra and breadth-first search
- Draw walls and set start and goal positions
- Adjust the animation speed
Worauf du achten solltest
- Dijkstra expands in an even circle; A* stretches towards the goal
- Both find a path of the same length, but A* checks far fewer squares
- Walls that force a detour make the two algorithms behave much more alike
Die Physik dahinter
Dijkstra's algorithm expands nodes in order of distance from the start, guaranteeing the shortest path but exploring a great deal of irrelevant territory. A* adds a heuristic estimate of the remaining distance, which steers the search towards the goal. Provided that heuristic never overestimates, A* still guarantees the shortest path while visiting far fewer nodes.