6. Networks and shortest paths

Lesson 6 of 6 · Networks and shortest paths

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.

Try it

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.

Can you find the route with the smallest total?
💡
Learning tip Don’t just look for the cheapest next edge. Try a few complete routes and add their weights. A choice that looks best at the beginning may lead to a more expensive route overall.
6 3 5 4 8 11 3 8 4 A B C D E F
Your route
A
Total
0
Best so far
—
Click a vertex joined to A.
Shortest route
A → B → D → E → F
6 + 4 + 3 + 4 = 17

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.

Definition

Weighted graph

A weighted graph is a graph in which each edge has a number, called its weight.

Definition

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.

Connection
How quickly do the possibilities grow?
Large networks can have far too many possible routes to check one by one. Counting & Combinatorics explores how collections of possibilities grow, and how to count them without listing every case.

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.

Dijkstra’s algorithm

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.

6 3 5 4 8 11 3 8 4 A 0 B ∞ C ∞ D ∞ E ∞ F ∞
Start at A. Its distance is 0. Every other distance begins at ∞ because we have not found a route there yet.
Method

Dijkstra’s algorithm

Keep beside each vertex the shortest distance from the start that you know so far. Then repeat these three moves:

1 · Start
S A B 0 ∞ ∞

Write 0 at the start and ∞ everywhere else.

2 · Improve
4 A B 6 12 → 10

From the current vertex, calculate current distance + edge weight. Replace a neighbour’s number only if this is smaller.

3 · Settle & repeat
A B C 4 6 9

Choose the unsettled vertex with the smallest number. Settle it: that distance is now final. Repeat.

Key idea: compare total distance from the start, not just the cheapest next edge.

Dijkstra’s algorithm works when edge weights are non-negative.

Let’s use it

Practice

Your turn: run Dijkstra’s algorithm

Find the shortest path from S to T. At each step, click the unsettled vertex with the smallest distance.
💡
Learning tip Before choosing the next vertex, pause and predict which one Dijkstra’s algorithm will select. Then check whether your prediction was right. Predicting each step is much more useful than simply following the completed calculation.
4 7 1 5 2 8 3 S 0 A ∞ B ∞ C ∞ T ∞
Which unsettled vertex has the smallest distance?

Weights can mean different things

Think about it

What could an edge weight mean?

The numbers on the edges do not have to mean kilometres. They can stand for many different things.

⏰
travel time
💷
cost
⛽
fuel use
💻
computer delay
⚠️
risk
⚡
energy use
Big idea:
A shortest-path problem really means: find the route with the smallest total weight.

Practice puzzles

Practice 1

Find the shortest path

What is the shortest path from A to E?

5 2 4 3 2 4 A B C D E
Reveal answer
A → C → D → E
2 + 3 + 4 = 9.
Practice 2

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?

5 2 4 8 2 4 A B C D E
Reveal answer
The new shortest path is A → C → B → D → E.

2 + 2 + 4 + 4 = 12.

So increasing the weight of just one edge can make a completely different route become best.

Practice 3

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?

5 4 3 2 4 A B C D E
Reveal answer
The new shortest path is A → B → D → E.

5 + 4 + 4 = 13.
Challenge

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.

Your graph should have:
  • 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.

Need a hint?

Start with two possible directions from S.

S A B C D T ? ? ? ? ? ?

Try making one edge out of S very cheap, but make the rest of that route expensive. Make the other first edge more expensive, but the rest of its route much cheaper.

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?

Printable resources
Graphs Lesson 6 printable maths resources
Lesson 6 Handout & Exercises

Download the printable examples, practice activities and answers for Networks and Shortest Paths.

Find the resources →
🎓 Graphs Certificate of Completion

Finished the course? Download and complete your Graphs Certificate of Completion.

Download your certificate →
Lesson 6 of 6 · Networks and shortest paths