Map Problem

The Challenge

You're a delivery driver on Computia Island.

Start at Port Alpha. Deliver to three towns. Return home.

What route minimises your total distance?

Look at the map. 30 seconds — first impressions?

Graph Vocabulary

Draw the Graph

In the box on your worksheet: draw circles for towns, lines for roads.

Write the distance on each line.

The map and the graph show the same information — just in different forms.

Systematic Shortest Path

Process (Dijkstra's approach):

• Start: Alpha = distance 0
• Look at all connected nodes — note their distances
• Visit the closest unvisited node
• Update distances to its neighbours if you found a shorter route
• Repeat until you've visited all nodes

Work Through It Together

From Alpha: Betaville = 8km, Gammaford = 15km, Delta Bay = 12km

Closest unvisited: Betaville (8km)

From Betaville: Gammaford via β = 8+6=14km ← shorter than 15! Update.

Epsilon via β = 8+10=18km. Note this.

Continue on your worksheet until all towns are found.

The Delivery Tour

Visit: Epsilon, Etaville, Iota, Kappa End — then return.

Try two different orderings. Which is shorter?

Is "always go to the nearest unvisited town" always optimal?

Spoiler: no. This is the Travelling Salesman Problem — one of CS's hardest.

Point-to-Point vs Tour

Shortest path (α to κ): Dijkstra's gives the exact correct answer. Efficient.

Shortest tour (visit all towns, return to start): No efficient algorithm is known. It's NP-hard — the number of possible routes explodes with n.

For 10 towns: 181,440 possible tours. For 20 towns: ~60 trillion.

Key Takeaway