AI HL · AHL 1
0 of 43 skills done
Weighted graphs and shortest routes
AHL 1.6
The graph shows the distances in km along the roads between five villages. Write down the weighted adjacency table.
Have a go first. Then open the working one line at a time.
Rows and columns A, B, C, D, E
Row = the vertex you leave, column = the vertex you reach. Put a dash on the diagonal: no road joins a village to itself.
AB = 7 goes in row A, column B and in row B, column A
The graph is undirected, so the table is symmetric. Use a dash where there is no road, such as A–C.
Table below
Check: each row's non-dash entries match the weights on the edges at that vertex.
50 × 2 = 100
The roads add to 50. Every road is in the table twice.
The table shows the weighted adjacency table of a directed graph. Each entry is the weight of the arrow from the row vertex to the column vertex. A dash means there is no arrow. Draw the graph.
Have a go first. Then open the working one line at a time.
A → B (5), A → C (8)
Each row lists the arrows leaving that vertex. Row A has two numbers, so two arrows leave A.
B → D (3); C → B (6); D → A (7), D → C (4)
Go along each row. Every number is one arrow from the row vertex to the column vertex.
Draw A, B, C, D, then each arrow with its weight
The table is not symmetric, so the arrows have a direction. Put the head at the column vertex.
5 + 8 + 3 + 6 + 7 + 4 = 33
There are 6 arrows, one for each number in the table.
The graph shows the times, in minutes, along the roads between a depot S and a shop T. Find the shortest route from S to T and its length.
Have a go first. Then open the working one line at a time.
S–B–D–T = 20; S–C–T = 23; S–C–D–T = 25
Start at S and never visit a vertex twice. Add the weights along each route.
S–A–C–T = 36; S–A–C–D–T = 38; S–B–D–C–T = 42
There are 6 routes in all. Writing them in a list stops you missing one.
Smallest total: 20 (route S–B–D–T); the next is 23
Choose the smallest total. Here it is unique.
Shortest route S–B–D–T, length 20 minutes
The route is in bold.
The graph shows the distances, in km, along the roads between a farm S and a market T. (a) Find the shortest route from S to T. (b) The road S–A is closed. Find the new shortest route and its length.
Have a go first. Then open the working one line at a time.
S–A–D–T = 14; S–B–T = 22; S–A–D–C–T = 33; S–B–C–D–T = 33 | S–B–C–T = 36; S–A–D–C–B–T = 41
List every route and add the weights.
S–A–D–T, length 14 km
The smallest total. It uses the road that will close.
Cross out S–A. Routes left: S–B–T = 22; S–B–C–D–T = 33; S–B–C–T = 36
Delete every route that uses the closed road. Do not search again from nothing.
New shortest route S–B–T, length 22 km
The journey is 8 km longer than before.
The table shows the cost, in £, of the direct flight between six airports. A dash means there is no direct flight. Find the cheapest way to travel from A to F, and its cost.
Have a go first. Then open the working one line at a time.
Each number is a weighted edge
A has only one direct flight, to E. Every route from A starts A–E.
A–E–C–F = 82; A–E–D–F = 95; A–E–B–F = 109; A–E–B–D–F = 134; A–E–B–C–F = 145 | A–E–C–B–F = 148; A–E–D–B–F = 170; A–E–C–B–D–F = 173; A–E–D–B–C–F = 206
Follow the numbers along rows and columns. Do not visit an airport twice.
A–E–C–F costs £82
Take the smallest total.