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.Higher 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? Three vertices joined in a triangle, with lengths AB = 2, BC = 3, AC = 8. Undirected: each edge works both ways. Every weight is positive. No units are given.
  • How must I do it? Dijkstra's algorithm, from A. A is the start; every distance is measured from A.
  • What do they want? Two things: the final label of every vertex (its shortest distance from A), and the shortest path to C (the route, not just its length).
Céim

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

Dijkstra's Shortest-Path Algorithm

Dijkstra’s algorithm finds shortest distances from a starting vertex by settling the smallest temporary label and updating its neighbours.

Why it matters

In an exam, a clear label table justifies shortest routes rather than merely guessing them from the diagram.

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? Three vertices joined in a triangle, with lengths AB = 2, BC = 3, AC = 8. Undirected: each edge works both ways. Every weight is positive. No units are given.
    • How must I do it? Dijkstra's algorithm, from A. A is the start; every distance is measured from A.
    • What do they want? Two things: the final label of every vertex (its shortest distance from A), and the shortest path to C (the route, not just its length).
  2. Understand

    • How do I picture it?
    • Draw the triangle. Put A at the bottom left, C at the bottom right, B on top. Write 2 on AB, 3 on BC, 8 on AC.
    • The edge AC goes straight to C: length 8. Is that the shortest way? Not always. A route with more edges can be shorter.
  3. Reduce

    • Where do I start?
    • Start: d(A) = 0. Every other label is ∞, 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.
  5. Check

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