AI Tutor
When you type a destination into a map app, your phone finds the fastest route out of millions of roads in a fraction of a second.
How does a computer test so many possible pathways without crashing?

Networks, Nodes, and Edges

In math and computer science, a network (also called a graph) is a collection of connected points.
Each point is called a node (or vertex), and each line connecting two nodes is called an edge.
When edges have numbers representing distance, time, or cost, we call those numbers weights.
What if your map isn't a messy web of roads, but a neat checkerboard city grid?

Grid Traversal and Distance

On a square grid, you can only move horizontally or vertically along grid lines, not diagonally.
The minimum number of grid steps between (x1,y1)(x_1, y_1) and (x2,y2)(x_2, y_2) is called the Manhattan distance, calculated as ∣x2−x1∣+∣y2−y1∣|x_2 - x_1| + |y_2 - y_1|.
On an open grid, any path that only moves toward the goal has the exact same minimum length.