Step 5 of 8 · Worked example · TEACH

← Algorithms, Optimisation & Project Scheduling

0 of 3 done

Work through the example to CHECK to open the problems.

Reach CHECK to open the problems.Ordinary Level · Applied Maths · Algorithms, Optimisation & Project Scheduling · Step 5

Follow the worked example and explain why each modelling and calculation step is valid.

An undirected triangle has AB=2, BC=3 and AC=8. Use Dijkstra from A to find final distance labels and the shortest path to C.

An undirected triangle has AB = 2, BC = 3 and AC = 8.

Use Dijkstra's algorithm from A. Find the final distance labels and the shortest path to C.

Read it once, slowly. Then copy it onto your page.
  • What is fixed? A triangle with lengths AB = 2, BC = 3, AC = 8. Undirected: each edge works both ways. Every length is positive.
  • How must I do it? Dijkstra's algorithm, from A. A is the start, so every distance is measured from A.
  • What do they want? The final label at every vertex, its shortest distance from A, and the shortest path to C: the route, not just the number.
Céim

Ordinary Level Applied Maths · Algorithms, Optimisation & Project Scheduling · Step 5 of 8

Dijkstra's Shortest-Path Algorithm

Dijkstra's algorithm finds shortest paths from a starting vertex by making the smallest temporary distance permanent and updating neighbouring distances.

Why it matters

Updating temporary labels prevents a direct edge or an early estimate from being mistaken for the shortest route.

The worked example

An undirected triangle has AB = 2, BC = 3 and AC = 8. Use Dijkstra's algorithm from A. Find the final distance labels and the shortest path to C.

How the worked example goes

  1. Read

    • What is fixed? A triangle with lengths AB = 2, BC = 3, AC = 8. Undirected: each edge works both ways. Every length is positive.
    • How must I do it? Dijkstra's algorithm, from A. A is the start, so every distance is measured from A.
    • What do they want? The final label at every vertex, its shortest distance from A, and the shortest path to C: the route, not just the number.
  2. Understand

    • How do I picture it?
    • Draw the triangle: A bottom left, B on top, C bottom right. Write each length on its edge.
    • The edge AC goes straight to C, length 8. Is that the shortest way? Not always.
  3. Reduce

    • Where do I start?
    • d(A) = 0. B and C get ∞, meaning not reached yet.
    • Settle, update, repeat until all 3 are settled. Each time a label improves, note the vertex it came from. That rebuilds the path.
  4. Solve

    • Settle A, then B.
    • Settle A: d(A) = 0.
    • Update B: 0 + 2 = 2, via A. Update C: 0 + 8 = 8, via A.
  5. Check

    • Is it right?
    • Every route from A
    • to C: A–C = 8, A–B–C = 2 + 3 = 5