Algorithms & Graph Search

How computers find good routes

See how a search algorithm compares routes, updates costs, and reliably finds a strong path through a network of choices.

Interactive Dijkstra Visualizer

Edit the graph, pick a start and target, then step through the algorithm. Toggle Wide to expand beyond the page margins and fit everything on one screen. Switch between SVG, Canvas, and 3D renderers.

Renderer

starttargetcurrentvisitedfrontierpathcycle

01/20

Speed

Edit Mode

Drag nodes · pan/zoom canvas

Templates

Graph Type

StartTarget

Trace · step 1/20

00 Initialize: dist[A] = 0, all others = ∞. Priority queue ← (0, A).

Priority Queue (min)

A:0

Distance Table

#	visit	B	C	D	E	F	G	H
0	init	∞	∞	∞	∞	∞	∞	∞
1	A	∞	∞	∞	∞	∞	∞	∞
2	A	4	∞	∞	∞	∞	∞	∞
3	A	4	∞	2	∞	∞	∞	∞
4	D	4	∞	2	∞	∞	∞	∞
5	D	4	∞	2	4	∞	∞	∞
6	B	4	∞	2	4	∞	∞	∞
7	B	4	9	2	4	∞	∞	∞
8	B	4	9	2	4	∞	∞	∞
9	E	4	9	2	4	∞	∞	∞
10	E	4	9	2	4	8	∞	∞
11	F	4	9	2	4	8	∞	∞
12	F	4	9	2	4	8	∞	∞
13	F	4	9	2	4	8	11	∞
14	F	4	9	2	4	8	11	14
15	C	4	9	2	4	8	11	14
16	G	4	9	2	4	8	11	14
17	G	4	9	2	4	8	11	13
18	H	4	9	2	4	8	11	13
19	done	4	9	2	4	8	11	13

Shortcuts: space play/pause ·←/→ step ·R reset ·V/N/E move/add/connect ·⌘Z undo ·del delete

Before We Begin

What we are learning today

Search is the hidden engine behind routing, planning, scheduling, and many game-like problems. Dijkstra's algorithm offers a clean first example because it keeps a running record of the cheapest known path to every location and improves those records until the best route is confirmed.

How this lesson fits

This module builds the mental model underneath everything else in the curriculum. We start with explicit rules, then add uncertainty, then explore search, so students can see AI as a chain of concrete decisions rather than a pile of mysterious buzzwords.

The big question

How can a machine move from rigid step-by-step instructions to making sensible choices in a messy, uncertain world?

Trace a computation step by step and explain why each move happensUse probability to talk about uncertainty instead of pretending outcomes are guaranteedDescribe how search algorithms compare options and settle on a good path forward

Why You Should Care

Before an AI system can act intelligently, it often has to evaluate many possible next moves. Search algorithms teach students how machines compare alternatives systematically rather than by intuition.

Where this is used today

✓Map and navigation apps that compute low-cost routes using time, distance, or traffic
✓Network routing systems that decide how data packets should travel across the internet
✓Game and robotics pathfinding, where an agent must move through space efficiently

Think of it like this

Imagine walking through a dim maze with a notebook. Every time you reach a junction, you write down how much it cost to get there. Instead of wandering randomly, you always continue from the cheapest unfinished option on your list. Order, not luck, is what gets you out.

Easy mistake to make

In graph search, 'shortest' does not have to mean the smallest physical distance. It means the lowest total cost according to whatever weights the system cares about, such as time, fuel, or risk.

By the end, you should be able to say:

Describe a graph using nodes, edges, and weights without relying on mathematical jargon
Explain how Dijkstra's algorithm relaxes edges and updates the best known distances
Connect shortest-path search to routing, robotics, scheduling, and planning problems

Think about this first

When a navigation app avoids the route that looks physically shortest, what hidden costs might it be optimizing instead? Name as many as you can.

Words we will keep using

graphnodeedgeweightshortest path

What is Dijkstra's Algorithm?

Dijkstra's algorithm answers a simple question: “What is the fastest way to get there?” It works like a cautious traveler who always explores the closest unfinished town first, keeping a running record of the cheapest known path to every place and improving those records until the best route is confirmed.

GraphThe map. A collection of places (nodes) and roads (edges).

WeightsThe cost. Distance, time, money — whatever you are trying to save.

Why AI caresBefore a robot moves, it plans. Search is the first step of action.

Algorithm Pseudocode

function dijkstra(graph, start):
  dist[start] = 0; dist[all others] = ∞
  pq = priority queue with (0, start)

  while pq not empty:
    (d, u) = pq.pop_min()
    for each neighbor v of u with edge weight w:
      if dist[u] + w < dist[v]:
        dist[v] = dist[u] + w
        pq.push((dist[v], v))

  return dist  // shortest distances from start

Do not worry too much about the formula yet. The big idea is that a smart data structure lets the algorithm stay efficient even on larger graphs.

Connections to AI

This idea appears everywhere in AI: robot navigation, game search, network routing, and even recommendation or knowledge systems. Once students understand shortest-path search, they have one of the core building blocks of intelligent planning.