Practice Maths

L39 — Network Applications

Key Terms

Critical path
The longest path through an activity network — it determines the minimum project completion time.
Activity network
A directed graph where edges are activities (with duration weights) and vertices are events or milestones.
Earliest start time
The earliest an activity can begin, determined by when all its predecessor activities finish.
Float (slack)
The amount an activity can be delayed without delaying the overall project; activities on the critical path have zero float.
Chinese postman problem
Finding the shortest route that traverses every edge at least once — relevant for route inspection problems.
Travelling salesman problem
Finding the shortest route that visits every vertex exactly once and returns to the start.

Real-world network problems

Problem typeGoalAlgorithm
Route planningFastest/cheapest path between two pointsDijkstra's shortest path
Infrastructure connectionConnect all nodes at minimum costKruskal's MST
Inspection routeTraverse every edge at least onceEuler path/circuit (Chinese Postman)
Critical pathMinimum time to complete a projectLongest path in a directed graph

Critical path analysis

Used in project management. Each activity is an edge; its weight is the duration. The critical path is the longest path from start to finish — it determines the minimum project completion time.

Activities on the critical path have zero float (no slack). Delaying them delays the entire project.

Network flow

In a flow network, each edge has a capacity (maximum flow). The maximum flow from source to sink equals the minimum cut (max-flow min-cut theorem).

3 2 5 4 1 4 3 S A B C D E Critical path (3+5+4=12 days) Non-critical
Activity network: critical path S→A→C→E takes 12 days (minimum project time).
Hot Tip: Activities on the critical path have zero float — any delay there delays the whole project. To find the critical path, identify all paths from start to finish and find the one with the greatest total duration.

Worked Example 1 — Route planning

A delivery driver starts at depot D and must visit warehouses A, B, C before returning. Road distances (km): D–A=10, D–B=15, D–C=20, A–B=8, A–C=12, B–C=9. Find the shortest route visiting all warehouses and returning to D.

Try all routes (small problem, try each):

D→A→B→C→D = 10+8+9+20 = 47 km.

D→A→C→B→D = 10+12+9+15 = 46 km.

D→B→A→C→D = 15+8+12+20 = 55 km.

Shortest route: D→A→C→B→D = 46 km.

Worked Example 2 — Critical path

Project activities with durations (days): Start→A(3), Start→B(2), A→C(5), B→C(6), C→End(4). Find the critical path.

Path S→A→C→End = 3+5+4 = 12 days.

Path S→B→C→End = 2+6+4 = 12 days.

Both paths are critical (tie). Minimum project time = 12 days.

Worked Example 3 — Choosing the right algorithm

A council has two problems: (a) laying water pipes to connect 6 suburbs at minimum cost; (b) finding the fastest ambulance route from the hospital to any suburb. Which algorithm for each?

(a) Connect all suburbs at minimum cost → Kruskal's MST.

(b) Fastest route from one source to all destinations → Dijkstra's shortest path.

See Answers ➔

  1. Choosing the right method. Fluency

    • (a) A gas company needs to connect 8 towns to a pipeline network at minimum cost. Which algorithm should they use?
    • (b) A GPS app finds the fastest route from home to work through a city. Which algorithm does it use?
    • (c) A garbage truck must collect from every street in a neighbourhood. What type of graph path must it find?
    • (d) A project manager wants to know the minimum time to complete a construction project. What analysis do they perform?

  2. Critical path. Fluency

    A project has activities: Start→A(4), Start→B(2), A→C(3), B→C(7), C→End(2).

    • (a) List all paths from Start to End.
    • (b) Find the duration of each path.
    • (c) Identify the critical path.
    • (d) What is the float (slack) for activity A?

  3. MST in context. Fluency

    A school needs to run cable connecting 5 computers. Cable costs ($/m): A–B=30, A–C=20, B–C=15, B–D=25, C–D=10, C–E=35, D–E=18.

    • (a) List edges in order of cost.
    • (b) Apply Kruskal's algorithm to find the MST.
    • (c) Find the minimum total cable cost.
    • (d) How much is saved compared to using all possible cables?

  4. Shortest path in context. Fluency

    Emergency response times (minutes) between locations: Hospital(H)–A=3, H–B=5, A–B=2, A–C=4, B–C=1, B–D=6, C–D=3.

    • (a) Use Dijkstra's algorithm to find the shortest time from H to D.
    • (b) What is the fastest route?
    • (c) If road A–B is closed, find the new shortest path from H to D.
    • (d) Which location is hardest to reach from H? Why?

  5. Critical path analysis. Understanding

    The diagram below shows an activity network for building a house. Durations are in weeks.

    2 4 6 3 1 5 5 3 S A B C D E F
    Activity network for house construction (durations in weeks). F is the finish node.
    • (a) List all paths from S to F.
    • (b) Find the duration of each path.
    • (c) State the critical path and the minimum project duration.
    • (d) Activity A→C takes 6 weeks. If a faster supplier reduces it to 4 weeks, does this shorten the project? Explain.

  6. Transport network. Understanding

    A city has 6 suburbs. Bus routes (with travel times in minutes): A–B=8, A–C=12, B–C=5, B–D=10, C–D=7, C–E=15, D–E=6, D–F=9, E–F=4.

    • (a) Find the shortest travel time from A to F using Dijkstra's algorithm.
    • (b) Write the fastest route.
    • (c) The city wants to minimise total route distance while keeping all suburbs connected. Find the MST using Kruskal's algorithm.
    • (d) A new express bus cuts A–F directly to 18 minutes. Does this change the shortest path?

  7. Chinese Postman application. Understanding

    A snow plough must clear all roads in a district. The road network has vertices (intersections) with degrees: 2, 4, 3, 3, 4, 2.

    • (a) Does an Euler circuit exist? Explain.
    • (b) If not, how many extra road passes are needed (minimum)?
    • (c) Which vertices cause the problem?
    • (d) If the two odd-degree vertices are connected by a road of length 0.8 km, what is the minimum extra distance the plough must travel?

  8. Network design trade-offs. Understanding

    • (a) A network engineer can either: (i) install the MST for $50 000 or (ii) install all possible connections for $120 000. What does the MST sacrifice compared to full connection?
    • (b) If one MST edge fails, what happens to connectivity? How does full connection handle this?
    • (c) Suggest when the extra cost of full connection is justified.
    • (d) A compromise is a network with MST + 2 extra edges. Explain the benefit.

  9. Project scheduling. Problem Solving

    A software project has activities (with durations in days and dependencies):

    • A: Requirements (3 days) — can start immediately
    • B: Design (5 days) — requires A
    • C: Database setup (4 days) — requires A
    • D: Front-end coding (6 days) — requires B
    • E: Back-end coding (7 days) — requires B and C
    • F: Testing (3 days) — requires D and E
    • G: Deployment (1 day) — requires F
    • (a) Draw the activity network.
    • (b) Find all paths from Start to End and their durations.
    • (c) Find the critical path and minimum project completion time.
    • (d) The client wants the project done 2 days earlier. Which activities could be accelerated to achieve this, and which would have no effect?

  10. Network optimisation. Problem Solving

    A water authority needs to design a pipe network for 7 towns. Connection costs ($000s): A–B=14, A–C=9, A–D=18, B–C=7, B–E=11, C–D=12, C–E=8, C–F=15, D–F=10, E–F=6, E–G=13, F–G=9.

    • (a) How many edges are in the MST?
    • (b) Apply Kruskal's algorithm to find the MST.
    • (c) Find the total MST cost.
    • (d) Town C is a central hub. If the cost of any edge connected to C increases by 30%, which (if any) MST edges change? Recalculate if needed.