Algorithms

Dijkstra is guaranteed to find the shortest path if all edge costs are non-negative. Advantage: optimal and without heuristics. Disadvantage: often visits a large number of nodes (can be slower for large grids). Wikipedia

A* extends Dijkstra with a heuristic (e.g. Manhattan distance) and can therefore search in a much more targeted manner. Advantage: often significantly faster with good heuristics; with permissible heuristics, the path remains optimal. Disadvantage: highly dependent on heuristics (poor heuristics ≈ Dijkstra). Wikipedia

Original work

• Edsger W. Dijkstra (1959): A note on two problems in connexion with graphs
• Peter E. Hart, Nils J. Nilsson, Bertram Raphael (1968): A Formal Basis for the Heuristic Determination of Minimum Cost Paths

How it works

The grid is a two-dimensional array of nodes. Each node stores its distance from the start, its predecessor and, for A*, the heuristic h and the sum f = g + h. Both algorithms run to the end first and return the list of visited nodes and the path. The animation then replays that list node by node with setTimeout.

• Dijkstra: all nodes sit in one list. Dijkstra sorts the whole list by distance in every step (O(n² log n)) and takes the next node. A heap would be faster; with at most 22,500 nodes this is enough here. If the next node has distance infinity, the goal cannot be reached.
• A*: same structure, but only the open list is sorted, by f = g + h; on equal f the smaller h wins. The heuristic is the Manhattan distance. It is admissible because each step costs 1 and there are only four directions, so the path stays optimal.
• The path is read at the end from the predecessor chain, from the goal back to the start.
• Compare mode: start, goal and walls are copied into a second grid. A* runs on the first, Dijkstra on the second, both animations run at the same time. The number of visited nodes shows the difference.
• Execution time is the search only, without the animation. Memory: one node object per cell, at most 150 × 150 = 22,500 nodes.

Source code:pathfinding.service.tspathfinding-animator.ts

Note This A* implementation is deliberately kept simple. It only moves in four directions and each step costs 1. The heuristic is minimal and only serves to demonstrate the principle of A* compared to Dijkstra. The goal is not an optimal or production-ready A* algorithm, but a clear visualisation of how heuristics can speed up the search.