Weighted graphs and shortest routes Problem set A One question at a time

The graph shows the distances, in km, along the roads between five villages. Write down the weighted adjacency table.

• Rows and columns A, B, C, D, E. Put a dash on the diagonal.
• Enter each weight twice: the graph is undirected, so the table is symmetric.
• Use a dash where there is no edge.
• Check the table is symmetric.

The directed graph shows the flight times, in hours, between four airports. Each arrow is a one-way route. Write down the weighted adjacency table.

• Row = the vertex the arrow leaves, column = the vertex it reaches.
• Enter each arrow once: A→B = 4, B→C = 6, C→D = 3, D→A = 5, A→D = 2, B→D = 7.
• The table is not symmetric because the arrows have a direction.

The table shows the walking time, in minutes, between five stalls at a market. A dash means there is no direct path.

1. (a) Draw the weighted graph.

   • The table is symmetric, so read each edge once from the entries above the diagonal.
   • Draw A, B, C, D, E and join them: AB (12), AC (9), BC (10), BD (7), CD (11), CE (6), DE (14).
   • Label each edge with its weight. Edges: 7.

2. (b) Which stall has the most direct paths?

   • Degrees: A = 2, B = 3, C = 4, D = 3, E = 2
   • Vertex C has the most edges, 4.

The table shows the cost, in dollars, of sending a parcel directly from one depot to another. Each entry is the cost from the row depot to the column depot. A dash means there is no direct service.

1. (a) Draw the weighted directed graph.

   • Read each row as the arrows that leave that vertex.
   • Draw A, B, C, D and the arrows: A→B (5), A→C (8), B→D (3), C→B (6), D→A (7), D→C (4).
   • Each number is one arrow, with its head at the column vertex.

2. (b) Find the total cost of the services that leave depot D.

   • Arrows leaving D: D→A (7), D→C (4)
   • 7 + 4 = 11

The graph shows the times, in minutes, along the roads between a bakery S and a cafe T. Find the shortest route.

1. (a) Find the shortest route from S to T.

   • List every route and add the weights:
   • S–B–D–T = 19; S–B–T = 24; S–A–B–D–T = 27; S–A–C–B–D–T = 31
   • S–A–B–T = 32; S–A–C–B–T = 36
   • Smallest total: S–B–D–T

2. (b) Write down its length.

   • S–B–D–T: 11 + 3 + 5 = 19 minutes

The graph shows the distances, in km, along the roads from a campsite S to a lake T.

1. (a) Find the shortest route from S to T and its length.

   • S–A–C–T = 15; S–A–C–D–T = 19; S–B–C–T = 27; S–A–C–B–T = 28
   • S–B–T = 28; S–B–C–D–T = 31
   • Shortest: S–A–C–T, 15 km

2. (b) The road S–A closes. Find the new shortest route and its length.

   • Remove every route that uses S–A.
   • Routes left: S–B–C–T = 27; S–B–T = 28; S–B–C–D–T = 31
   • New shortest: S–B–C–T, 27 km

The table shows the cost, in £, of the direct train ticket between six cities. A dash means there is no direct train. Find the cheapest route from A to F, and its cost.

• Read each number as an edge with that weight. A dash means no direct link.
• List the routes from A to F: A–B–C–F = 45; A–D–F = 47; A–C–F = 48; A–B–D–F = 52; A–D–B–C–F = 70 | A–C–B–D–F = 79; A–B–E–D–F = 110; A–D–E–B–C–F = 128; A–C–B–E–D–F = 137
• Smallest total: A–B–C–F = £45

The table shows the journey times, in minutes, between six stations. A dash means no direct train.

1. (a) Find the shortest route from A to F and its length.

   • Routes from A to F: A–C–E–F = 52; A–C–E–D–F = 58; A–E–F = 65; A–E–D–F = 71; A–C–F = 72 | A–B–F = 74; A–E–C–F = 115
   • Smallest total: A–C–E–F = 52 minutes

2. (b) Station C is closed and no route can pass through it. Find the new shortest route and its length.

   • Delete every route through C.
   • Routes left: A–E–F = 65; A–E–D–F = 71; A–B–F = 74
   • New shortest: A–E–F = 65 minutes