All Tools
STEM

Graph Theory & Pathfinding Visualizer

Explore, step through, and analyze classic graph search algorithms (A*, Dijkstra, BFS, DFS, Greedy BFS) on dynamic 2D grid topologies with obstacles, weighted terrain, and procedural mazes.

Graph Theory Computer Science
Brush:
Legend: Start Node Target Node Wall (Obstacle) Mud / Swamp (Cost: 5) Frontier / Open Set Visited / Closed Shortest Path Tip: Drag Start/Target pins to test paths dynamically!
No Path Found
Live Search Telemetry Ready
Path Cost
—
Path Length
—
Nodes Explored
0
Search Time
0 ms
Algorithm Status: Ready
Select an algorithm and click Visualize Path to begin search traversal, or click Step to inspect frontier expansion one node at a time.
Active Node Inspector (Hover on Grid)
g-Cost (Start) ∞
h-Cost (Heuristic) ∞
f-Cost (Total) ∞
A* Search (A-Star)
Combines actual path cost g(n) with estimated distance h(n) to target. Guarantees shortest path if heuristic is admissible and consistent.
Guaranteed Shortest: Yes Weighted: Yes Data Structure: Min-Heap
Shortest-Path & Graph Search Complexity Matrix
Algorithm Weighted Graphs? Guaranteed Shortest? Time Complexity (Worst) Space Complexity Primary Data Structure
A* Search Yes Yes (Admissible h) O(E + V log V) O(V) Min-Priority Queue (Binary Heap)
Dijkstra's Algorithm Yes Yes (Non-negative weights) O(E + V log V) O(V) Min-Priority Queue (Binary Heap)
Breadth-First Search (BFS) No (Uniform only) Yes (Fewest Edges) O(V + E) O(V) FIFO Queue (First-In First-Out)
Depth-First Search (DFS) No No (Path can be poor) O(V + E) O(V) (Tree Depth) LIFO Stack (Call Stack)
Greedy Best-First Search Yes No (Can get trapped) O(V log V) O(V) Min-Priority Queue (Keyed on h)
Bidirectional BFS No (Uniform only) Yes O(bd/2) O(bd/2) Dual FIFO Queues
Heuristic Metrics & Mathematical Admissibility
1. Manhattan Distance (L1 Norm)
h(u, v) = |x1 − x2| + |y1 − y2|

Standard distance metric for 4-directional grid graphs where diagonal traversal is forbidden (taxicab geometry). It computes the minimal orthogonal moves required to reach the target.

2. Euclidean Distance (L2 Norm)
h(u, v) = √((x1 − x2)2 + (y1 − y2)2)

Straight-line ruler distance in continuous Euclidean space. Always admissible because straight-line distance is the shortest possible path between any two points.

3. Chebyshev Distance (L∞ Norm)
h(u, v) = max(|x1 − x2|, |y1 − y2|)

Optimal metric for 8-directional movement (King's movement in chess), where orthogonal and diagonal steps each cost 1 unit of traversal.

Admissibility & Consistency Conditions:
  • Admissibility: An estimated heuristic h(n) is admissible if it never overestimates the true minimal cost h*(n) to reach the goal: h(n) ≤ h*(n). This guarantees that A* never bypasses an optimal path.
  • Consistency (Monotonicity): For every node u and successor v connected by edge weight c(u, v): h(u) ≤ c(u, v) + h(v). If consistent, nodes expanded by A* never need to be re-opened in the closed set.
Graph Theory & Edge Relaxation Fundamentals
Grid as an Implicit Graph G = (V, E)

In computer science, a 2D tile grid represents an implicit planar graph:

  • Vertices V: Every cell (x, y) represents a vertex with coordinates and state.
  • Edges E: Connections exist between adjacent cells unless blocked by wall obstacles.
  • Edge Weights w(u, v): Normal floor tiles have weight w = 1; mud/swamp tiles have weight w = 5.
The Edge Relaxation Principle

The fundamental building block of Dijkstra's algorithm and A*:

if (dist[u] + weight(u, v) < dist[v]) {
  dist[v] = dist[u] + weight(u, v);
  parent[v] = u;
}

By relaxing edges and always extracting the minimum-cost node from a Priority Queue, Dijkstra's algorithm iteratively discovers the true shortest path to every reachable vertex.