Graphs are not just mathematical puzzles.
They can represent road systems, train networks, computer networks, delivery routes and many other real-world systems.
Often the important question is:
What’s the quickest way?
Imagine these vertices are places and the numbers on the edges are travel times.
You want to get from A to F. Which route has the smallest total travel time?
Don’t assume the route with the fewest edges is the fastest.
Find the quickest route from A to F
The number beside each edge tells you how long that journey takes. Click neighbouring vertices to build a route from A to F.
💡
Weighted graphs
In the graph above, the edges had numbers attached to them. Those numbers could represent travel time, distance, cost, or anything else we want to measure.
Weighted graph
A weighted graph is a graph in which each edge has a number, called its weight.
Shortest path
The weight of a path is the sum of the weights of all its edges.
A shortest path between two vertices is a path whose total weight is as small as possible.
How can we be sure we found the shortest path?
Trying lots of routes works on a small graph, but it quickly becomes impossible on a large network.
We need a method that guarantees we find the shortest path without checking every possible route.
One famous method is Dijkstra’s algorithm. It works by gradually discovering the shortest distance from the starting vertex to every other vertex.
Find the shortest path step by step
We start at A. Each vertex keeps track of the shortest distance we have found to it so far.
Dijkstra’s algorithm
- Give the starting vertex distance 0. Give every other vertex distance ∞.
- Choose the unsettled vertex with the smallest distance.
- Look at each of its neighbours. If going through this vertex gives a shorter route, replace the neighbour’s distance.
- Mark the vertex as settled and repeat.
- Stop when the destination is settled.
Dijkstra’s algorithm works when edge weights are non-negative.
Let’s use it
Your turn: run Dijkstra’s algorithm
💡
Weights can mean different things
What could an edge weight mean?
The numbers on the edges do not have to mean kilometres. They can stand for many different things.
A shortest-path problem really means: find the route with the smallest total weight.
Practice puzzles
Find the shortest path
What is the shortest path from A to E?
Reveal answer
2 + 3 + 4 = 9.
A journey gets slower
Start with the same network, but now the journey from C to D takes 8 instead of 3.
What is the new shortest path from A to E?
Reveal answer
2 + 2 + 4 + 4 = 12.
So increasing the weight of just one edge can make a completely different route become best.
Road closed
Return to the original network. Now the edge from A to C is closed.
What is the new shortest path from A to E?
Reveal answer
5 + 4 + 4 = 13.
Can you trick the greedy traveller?
💡
Learning tip
When designing your graph, work backwards from the behaviour you want.
First decide which route should really be shortest. Then choose weights
that make another route look tempting at the beginning.
💡
Design your own weighted graph with a starting vertex S and a destination T.
Make the cheapest edge leaving S lead in the wrong direction: the shortest path from S to T must begin with a more expensive edge.
- at least 5 vertices,
- at least two different routes from S to T,
- a positive weight on every edge,
- a cheapest first edge that is not part of the shortest route.
When you are finished, use Dijkstra’s algorithm to prove which route is really shortest.
What have we learned?
Graphs can represent real networks.
Numbers on edges are called weights.
The weight of a route is found by adding the weights of all its edges.
The shortest path is the route with the smallest total weight.
Algorithms such as Dijkstra’s algorithm allow computers to find shortest paths even in very large networks.
You have reached the end of Graphs
We started with nothing more than dots and lines.
Along the way, we used them to solve bridge puzzles, understand one-stroke drawings, colour maps and find routes through networks.
That is one of the remarkable things about graph theory: an extremely simple idea can describe an enormous variety of problems.
Where else can you spot a graph?
Think about friendships, transport maps, websites, computer networks, family trees or games. What should the vertices and edges represent?
Come back to it later
When you learn something new, it is important to come back to it later. Revisiting an idea after some time has passed helps you discover what you remember, what needs another look, and often makes the idea clearer the second time around. Our handouts are a perfect excuse to do exactly that.
Printable Graphs course
Prefer paper, a tablet, or studying offline? Open the printable version of the whole Graphs course, including this lesson.
Open printable PDF →Additional practice
Extra problems and investigations for this lesson are being prepared. Come back later for another chance to practise the ideas.
What did you think?
Whether you explored this together or worked independently, we would love to hear from both learners and parents. Tell us what you enjoyed, what was confusing, or what you would like to see next.
Share your feedback
The form is short and you do not need to give your name.