Weighted graphs and shortest routes Problem set B Worked solutions

The graph shows the walking times, in minutes, between five rooms in a museum. 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 lengths, in km, of four one-way cycle tracks between four parks. Write down the weighted adjacency table.

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

The table shows the length, in metres, of the cable between five lamp posts in a garden. A dash means there is no direct cable.

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: AC (8), AE (15), BC (13), BD (6), CD (10), CE (12), DE (9).
   • Label each edge with its weight. Edges: 7.

2. (b) Which lamp post has the most cables?

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

The table shows the time, in minutes, of the direct ferry between four islands. Each entry is the time from the row island to the column island. A dash means there is no direct ferry.

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→D (6), B→A (4), B→C (9), C→D (5), D→B (8), C→A (3).
   • Each number is one arrow, with its head at the column vertex.

2. (b) Find the total time of the ferries that leave island B.

   • Arrows leaving B: B→A (4), B→C (9)
   • 4 + 9 = 13

The graph shows the distances, in km, along the paths between a hut S and a summit T. Find the shortest route.

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

   • List every route and add the weights:
   • S–B–C–T = 15; S–A–C–T = 16; S–A–T = 18; S–B–C–A–T = 27
   • S–B–C–D–T = 39; S–A–C–D–T = 40
   • Smallest total: S–B–C–T

2. (b) Write down its length.

   • S–B–C–T: 5 + 6 + 4 = 15 km

The graph shows the times, in minutes, along the roads from a school S to a stadium T.

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

   • S–B–D–T = 19; S–D–T = 20; S–B–D–A–T = 27; S–D–A–T = 28
   • S–B–D–A–C–T = 34; S–D–A–C–T = 35
   • Shortest: S–B–D–T, 19 minutes

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

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

The table shows the cost, in euros, of the direct bus ticket between six towns. A dash means there is no direct bus. 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–D–C–F = 86; A–D–B–C–F = 122; A–B–D–C–F = 137; A–D–B–E–C–F = 138; A–E–C–F = 138 | A–B–C–F = 145; A–B–E–C–F = 161; A–E–B–D–C–F = 172; A–E–B–C–F = 180
• Smallest total: A–D–C–F = 86 euros

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

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

   • Routes from A to F: A–E–C–F = 46; A–F = 51; A–C–F = 64; A–E–B–F = 97; A–E–C–D–F = 116 | A–C–D–F = 134; A–C–E–B–F = 145
   • Smallest total: A–E–C–F = 46 minutes

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

   • Delete every route through E.
   • Routes left: A–F = 51; A–C–F = 64; A–C–D–F = 134
   • New shortest: A–F = 51 minutes