IB MYP 4-5 Maths- Weighted networks- Study Notes - New Syllabus
IB MYP 4-5 Maths- Weighted networks – Study Notes
Extended
- Weighted networks
IB MYP 4-5 Maths- Weighted networks – Study Notes – All topics
Weighted Networks
Weighted Network
A weighted network is a graph where each edge has a numerical value (weight) representing distance, cost, time, or any quantity associated with that connection.
Key Features
- Nodes (Vertices): Represent locations, points, or entities.
- Edges (Arcs): Connect nodes and represent paths or routes.
- Weights: Numbers on edges that represent distance, cost, or time.
Applications
- Transportation routes (shortest distance)
- Internet data routing (minimum latency)
- Supply chain optimization
- Project management (minimum time)
How to Solve Problems in Weighted Networks
Step 1: Draw the network with all weights labeled.
Step 2: Identify what you need: shortest path, minimum cost, etc.
Step 3: Use an appropriate algorithm (e.g., Dijkstra’s algorithm for shortest path).
Step 4: Show working step by step.
Example :
A network connects nodes A, B, and C with weights: A–B = 5, B–C = 7, A–C = 10. Find the shortest route from A to C.
▶️ Answer/Explanation
Solution:
Two possible routes:
- Direct: A → C = 10
- Via B: A → B → C = 5 + 7 = 12
Shortest Path: Direct route A → C (10 units).
Example :
Find the shortest path from node A to all other nodes in the weighted network:
Connections:
A–B = 4, A–C = 2, B–C = 1, B–D = 5, C–D = 8, C–E = 10, D–E = 2.
▶️ Answer/Explanation
Step 1: Initialize
Start from A. Distance to A = 0; others = ∞.
Step 2: Update distances
- From A: B = 4, C = 2
- Choose smallest unvisited: C (2)
Step 3: From C: Update B (via C): 2 + 1 = 3 (smaller than 4), D = 10, E = 12
Step 4: From B: D = min(10, 3 + 5) = 8
Step 5: From D: E = min(12, 8 + 2) = 10
Final Shortest Distances:
- A → A = 0
- A → C = 2
- A → B = 3
- A → D = 8
- A → E = 10
Example:
Find the shortest path from A to all other nodes in the following weighted network:
A–B = 4, A–C = 2, B–C = 1, B–D = 5, C–D = 8, C–E = 10, D–E = 2.
▶️ Answer/Explanation
Step 1: Initialize Table
| Node | Distance | Previous |
|---|---|---|
| A | 0 | – |
| B | ∞ | – |
| C | ∞ | – |
| D | ∞ | – |
| E | ∞ | – |
Step 2: Update Neighbors of A
- B = 4, C = 2
Step 3: Visit C (smallest distance = 2)
- B via C = 3 (smaller than 4 → update)
- D = 10, E = 12
Step 4: Visit B
- D = min(10, 3 + 5 = 8)
Step 5: Visit D
- E = min(12, 8 + 2 = 10)
Final Distances: A:0, C:2, B:3, D:8, E:10
Example:
A delivery truck needs to start from city A and reach city F with minimum distance. The connections are:
A–B = 3, A–C = 6, B–C = 2, B–D = 4, C–D = 1, D–E = 5, E–F = 3, C–F = 10.
▶️ Answer/Explanation
Apply Dijkstra’s algorithm step by step:
- Start at A: B = 3, C = 6
- Visit B: Update C = 5, D = 7
- Visit C: Update D = 6, F = 15
- Visit D: Update E = 11
- Visit E: Update F = 14
Shortest Distance to F = 14 units via A → B → C → D → E → F.