Weighted graphs and shortest routes Problem set B Answers

\(\begin{array}{c|ccccc} & A & B & C & D & E \\ \hline A & \text{–} & 12 & \text{–} & 9 & \text{–} \\ B & 12 & \text{–} & 6 & 14 & 7 \\ C & \text{–} & 6 & \text{–} & 8 & 10 \\ D & 9 & 14 & 8 & \text{–} & \text{–} \\ E & \text{–} & 7 & 10 & \text{–} & \text{–}\end{array}\)

\(\begin{array}{c|cccc} & A & B & C & D \\ \hline A & \text{–} & 9 & \text{–} & \text{–} \\ B & \text{–} & \text{–} & 5 & 3 \\ C & 12 & \text{–} & \text{–} & 8 \\ D & 6 & \text{–} & \text{–} & \text{–}\end{array}\)

1. (a) Edges: AC (8), AE (15), BC (13), BD (6), CD (10), CE (12), DE (9)
2. (b) Vertex C, degree 4

1. (a) Arrows: A→D (6), B→A (4), B→C (9), C→D (5), D→B (8), C→A (3)
2. (b) 13

1. (a) S–B–C–T
2. (b) 15 km

1. (a) S–B–D–T, 19 minutes
2. (b) S–B–D–A–T, 27 minutes

A–D–C–F, 86 euros

1. (a) A–E–C–F, 46 minutes
2. (b) A–F, 51 minutes