Skip to content
Workshopy.io
Join a classSign inStart free
  • Official
  • Beginner
  • English
  • About 75 min
  • 10 steps · 2 quizzes

Graphs & Shortest Paths — How Maps Find Your Route

A hands-on first look at graphs — the data structure behind maps, social networks and the internet — and the searches that find routes through them…

Start learningSee the steps
  • Free
  • No account needed
  • Stop any time, pick up where you left off
0 comments
Workshopy.io

WorkshopyOfficial

28 lessons · used by 2 teachers

For teachers

Teaching this? Run it live with your class.

  • Students join with a code — no accounts
  • See who’s done and who’s stuck, step by step
  • It’s your copy — change anything before class
Use this lesson

Sign in to copy it to your workspace. It’s free.

Your path

10 steps · 2 quizzes · about 75 minutes · open any step

  1. Everything is connected: nodes and edgesStart hereA graph is a set of nodes (things) joined by edges (connections). People and friendships. Stations and tracks. Web pages and links. Try it: tap a person. Then switch to the metro map and tap Center.InteractiveHands-on · 6 min
  2. One-way streets and travel timesTwo extra details turn a plain graph into a road map: - Directed: an edge has a direction (A → B, but not back). One-way streets, "follows" on social apps, links between web pages. - Weighted: an edge carries a number: minutes, kilometres, cost.InteractiveHands-on · 6 min
  3. Storing a graph: list or matrix?A program has to keep the graph in memory. Two classic ways: - Adjacency list: for each node, the list of its neighbours. - Adjacency matrix: an n × n grid; a 1 in row A, column B means there's an edge A–B.InteractiveHands-on · 6 min
  4. Breadth-first search: a waveHow do you explore a graph without getting lost? Breadth-first search (BFS) spreads like a ripple: first every neighbour, then their neighbours, and so on. It keeps the nodes still to visit in a queue: first in, first out.InteractiveHands-on · 6 min
  5. Fewest hops: remember who found youTo get an actual route, every node writes down who found it. When the wave reaches the target, walk backwards: the target was found by X, X by Y… all the way to the start. Try it: pick a different start and end.InteractiveHands-on · 6 min
  6. Check: graphs and BFSQuiz · 4 questions
  7. Fewest roads isn't fastestOn a real map, roads aren't equal: one takes 30 minutes, another 3. BFS counts hops, not minutes. Try it: guess which route wins, then press Race!InteractiveHands-on · 6 min
  8. Dijkstra's algorithm, step by stepEdsger Dijkstra found the method in 1956 (he later said he designed it in about twenty minutes, over a cup of coffee). Keep a table of the shortest time found so far to each place: 1. Start: 0 for the start, ∞ for everything else. 2.InteractiveHands-on · 7 min
  9. Your city, with live trafficA navigation app does the same thing, millions of times a day, with live traffic as the weights. Try it: tap a start, then a destination. Then drag the traffic slider for the Main bridge and watch the route jump to another bridge.InteractiveHands-on · 6 min
  10. Depth-first search and mazesDepth-first search (DFS) does the opposite of BFS: follow one path as far as it goes, back up at a dead end, then try the next turn. It keeps its places to visit on a stack: last in, first out. Try it: press Solve both.InteractiveHands-on · 6 min

Comments 0

You’ll sign in with Google before it’s posted.Comments are public — don’t name your students.
0 / 1,500

No comments yet. Be the first to say how it went.

Using it

Workshopy shares this lesson under CC BY 4.0. Anyone may use and change it, with credit to you. Anyone can learn it here, free. A copy in your workspace is yours to change and run live; your students never need an account.

Versions

  1. 1

    Version 1Current

    · First published

Copies are made from the current version. A copy you already have doesn’t change.

More from Workshopy

All 28 lessons