Practice Maths

L38 — Shortest Paths and Spanning Trees

Key Terms

Walk
A sequence of vertices and edges in a graph where vertices and edges may be repeated.
Path
A walk with no repeated vertices or edges.
Shortest path
The path between two vertices with minimum total edge weight; found using Dijkstra's algorithm.
Spanning tree
A subgraph that connects all n vertices with no cycles, using exactly n−1 edges.
Minimum spanning tree (MST)
The spanning tree with the smallest total edge weight; found using Prim's or Kruskal's algorithm.
Cycle
A closed path that starts and ends at the same vertex without repeating any edges or intermediate vertices.

Paths and walks

TermDefinition
WalkAny sequence of vertices and edges (can repeat)
TrailA walk where no edge is repeated
PathA walk where no vertex is repeated
CycleA path that starts and ends at the same vertex

Euler paths and circuits

TypeUses every edge exactly onceCondition
Euler pathYes (starts and ends at different vertices)Exactly 2 odd-degree vertices
Euler circuitYes (starts and ends at same vertex)All vertices even degree

Minimum spanning tree (MST)

A spanning tree connects all n vertices using exactly n−1 edges with no cycles. The minimum spanning tree is the spanning tree with the lowest total weight.

Kruskal's algorithm: add edges in order of increasing weight, skipping any that would create a cycle.

Dijkstra's algorithm (shortest path)

Finds the shortest path from a source vertex to all others in a weighted graph with non-negative weights.

  1. Assign distance 0 to the source, ∞ to all others.
  2. Visit the unvisited vertex with the smallest current distance.
  3. Update neighbouring distances if a shorter path is found.
  4. Repeat until all vertices are visited.
3 4 2 5 8 9 7 A B C D E MST edges (total = 14) Excluded edges
MST shown in blue (total weight 14). Dashed grey edges are excluded — adding any would create a cycle.
Hot Tip: A spanning tree for n vertices always has exactly n−1 edges. More edges means a cycle exists; fewer means some vertices are disconnected. Use this count to verify your minimum spanning tree.

Worked Example 1 — Euler path/circuit test

Determine whether the graph with edges AB, AC, BC, BD, CD has an Euler path or circuit.

Degrees: deg(A)=2, deg(B)=3, deg(C)=3, deg(D)=2. Two odd-degree vertices (B and C).

→ Euler path exists (starting at B or C), but no Euler circuit.

Worked Example 2 — Kruskal's MST

Find the MST for: AB=4, AC=2, AD=8, BC=5, BD=3, CD=6.

Sort edges: AC=2, BD=3, AB=4, BC=5, CD=6, AD=8.

Add AC(2): {A,C}. Add BD(3): {B,D}. Add AB(4): joins {A,C} and {B,D} — no cycle. Add BC(5): would create cycle A–B–C–A. Skip. Add CD(6): skip (cycle). Done (4 vertices, 3 edges).

MST: AC, BD, AB. Total weight = 2+3+4 = 9.

Worked Example 3 — Dijkstra's algorithm

Find the shortest path from A to D in: AB=3, AC=6, BC=2, BD=5, CD=1.

Start: A=0, B=∞, C=∞, D=∞.

Visit A: update B=3 (via A), C=6 (via A).

Visit B (dist 3): update C=min(6, 3+2)=5, D=min(∞, 3+5)=8.

Visit C (dist 5): update D=min(8, 5+1)=6.

Visit D (dist 6). Done. Shortest path A→B→C→D = 6.

Worked Example 4 — Why MST is useful

A council needs to connect 4 water towers. Cable costs match edge weights. Why use MST rather than installing all possible cables?

All cables: maximum connectivity but maximum cost, with redundant paths adding no value.

MST: all towers connected with minimum total cost, exactly n−1 = 3 cables, no cycles.

See Answers ➔

  1. Euler paths and circuits. Fluency

    • (a) A graph has all vertices with even degree. Does it have an Euler path, Euler circuit, both, or neither?
    • (b) A graph has exactly 2 odd-degree vertices. Does it have an Euler path, Euler circuit, both, or neither?
    • (c) A graph has 4 odd-degree vertices. Is an Euler path or circuit possible?
    • (d) For the graph with edges AB, BC, CD, DA, AC: find the degrees and determine if an Euler circuit exists.

  2. Kruskal's algorithm. Fluency

    A graph has edges: AB=7, AC=3, AD=10, BC=4, BD=6, CD=8.

    • (a) List the edges in order of increasing weight.
    • (b) Apply Kruskal's algorithm to find the MST.
    • (c) State the total weight of the MST.
    • (d) How many edges does the MST have?

  3. Dijkstra's algorithm. Fluency

    A graph has edges: AB=5, AC=2, BC=3, BD=8, CD=4.

    • (a) Set up the initial distance table from source A.
    • (b) Apply Dijkstra's algorithm step by step.
    • (c) State the shortest distance from A to D.
    • (d) Write the shortest path from A to D.

  4. Spanning trees. Fluency

    • (a) How many spanning trees does a simple path graph on 4 vertices have?
    • (b) A connected graph has 7 vertices. How many edges does any spanning tree of it have?
    • (c) True or false: a spanning tree of a graph includes all vertices of the graph.
    • (d) If a spanning tree has total weight 25 and you add one more edge of weight 8, what is the total weight? Is it still a spanning tree?

  5. Shortest path on a network diagram. Understanding

    Use the weighted network below to find the shortest path from A to F.

    4 6 3 5 8 2 7 4 A B C D E F
    Find the shortest path from A (blue) to F (red).
    • (a) Set up the initial distance table (A=0, all others=∞).
    • (b) Show the first two steps of Dijkstra’s algorithm.
    • (c) Find the shortest distance from A to F.
    • (d) Write the shortest path route.

  6. MST on a network. Understanding

    Use the graph from Q5. Apply Kruskal's algorithm to find the MST.

    • (a) List all edges in order of weight.
    • (b) Apply Kruskal's algorithm, showing which edges are added and which are skipped.
    • (c) State the total weight of the MST.
    • (d) Compare the MST total weight to the shortest path A to F. Explain why they are different concepts.

  7. Euler paths in context. Understanding

    A postman must walk every street in a suburb exactly once. The street network has vertices (intersections) with degrees: 4, 4, 2, 4, 2, 2.

    • (a) How many odd-degree vertices are there?
    • (b) Can the postman complete the route without repeating any street and return to the starting point?
    • (c) If two odd-degree vertices were added to the network, could an Euler circuit exist?
    • (d) The Chinese Postman Problem says: if the graph has 2k odd-degree vertices, you must repeat at least k paths. How many streets must be repeated if there are 4 odd-degree vertices?

  8. Comparing algorithms. Understanding

    • (a) What is the difference between a shortest path and a minimum spanning tree?
    • (b) If a graph has only one spanning tree, what type of graph must it be?
    • (c) Can the shortest path between two vertices be part of the MST? Give an example or counterexample.
    • (d) A delivery driver wants the most efficient route visiting 5 stops. Would you use shortest-path or MST? Explain.

  9. Network planning. Problem Solving

    A phone company needs to lay cable connecting towns A, B, C, D, E. Costs ($000): AB=15, AC=10, AD=20, AE=18, BC=12, BD=8, BE=14, CD=9, CE=11, DE=16.

    • (a) How many possible spanning trees exist (approximately)?
    • (b) Apply Kruskal's algorithm to find the MST.
    • (c) Find the total cost of the MST.
    • (d) Verify the MST has the correct number of edges.

  10. Königsberg bridge problem. Problem Solving

    The historic Königsberg bridge problem: the city had 4 land masses (A, B, C, D) connected by 7 bridges. The degree sequence was: deg(A)=3, deg(B)=3, deg(C)=5, deg(D)=3.

    • (a) How many odd-degree vertices are there?
    • (b) Can a person cross every bridge exactly once and return to the start? Justify using Euler’s theorem.
    • (c) Can they cross every bridge exactly once without needing to return to the start? Justify.
    • (d) How many bridges would need to be added or removed to make an Euler circuit possible?