Community resourceWorksheet

OCR H446 2.3.1 Dijkstra shortest paths

Part 13 of 16 · H446 2.3.1 · Algorithms

Dijkstra appears in H446 2.3.1 as something students calculate and trace rather than write from scratch, so the examined skill is holding tentative distances, later improvements and predecessors accurately. This worksheet keeps that whole state visible on a weighted graph and finishes with students building and verifying a graph of their own.

Students will:

  • maintain tentative and final distances alongside a predecessor for each node
  • record every improvement made to a distance when a shorter route is offered
  • give a finalisation order and reconstruct a shortest path from the predecessors
  • diagnose selecting the smallest edge, settling a node too early and negative weights
  • design a five-node graph with competing routes and verify the result by summing edges

Inside: 6 explanation cells, 1 multiple-choice question, 1 fill-in-the-blanks cell, 3 written answers and 1 trace table. 32 marks, about 30 to 45 minutes.

Series: H446 2.3.1 · Algorithms, part 13 of 16.

Shared by Coding PathwayVerified teacher

  • 12 cells
  • About 30 minutes
  • CC BY-SA 4.0
  • Shared 31 Aug 2026
  • Updated 3 Sept 2026

Preview

The whole resource, exactly as a class sees it. Answers and marking are held back.

Dijkstra shortest paths

Dijkstra finds minimum total weight from a start node when edge weights are non-negative. OCR expects calculation and tracing rather than necessarily writing the whole algorithm from scratch.

By the end, you will be able to

  • maintain tentative and final distances;
  • relax edges using cumulative route cost;
  • record predecessors and reconstruct a path;
  • state the non-negative-weight condition.

Reactivate: a weighted path cost is the sum of its edge weights.

Weighted graph and state invariant

Weighted graph for Dijkstra shortest-path modelling42158102ABCDETentative distance = best total from A found so far; finalise the smallest unsettled value.

Initialise A=0 and every other distance as infinity. Repeatedly finalise the unsettled node with smallest tentative distance. For each neighbour, candidate = current distance + edge weight; update only if candidate is smaller, recording the current node as predecessor.

Multiple choice1 mark

From A, C has final distance 2. Edge C-B has weight 1. What candidate distance is offered to B?

  • A3
  • B1
  • C2
  • D4

Worked opening iterations

Start: A=0; B,C,D,E=∞. Finalise A: B=4 via A, C=2 via A. Finalise C next: B improves to 3 via C; D=10 via C; E=12 via C. Finalise B: D improves to 8 via B. The smallest unsettled distance, not the fewest edges, controls selection.

Written answer12 marks

Complete Dijkstra from A on the displayed graph. Give finalisation order, final distance to every node, predecessor for each reachable non-start node, and shortest path A to E.

Show every offered distance and each later improvement rather than only final answers.

Students type their answer here.

Trace table4 marks

Trace this relaxation fragment after A has been processed.

Enter a value only when it changes. Record output in order.

Use one row for each pass through the loop. Fill in a box only when that value changes on that row, and leave the rest blank.

ProgramPython
  1. distance = {'B':4,'C':2,'D':999}
  2. current = 'C'
  3. current_distance = distance[current]
  4. neighbours = ['B','D']
  5. weights = [1,8]
  6. for index in range(len(neighbours)):
  7. neighbour = neighbours[index]
  8. weight = weights[index]
  9. candidate = current_distance + weight
  10. if candidate < distance[neighbour]:
  11. distance[neighbour] = candidate
  12. print(distance)
Trace table with 11 columns
Rowdistancecurrentcurrent_distanceneighboursweightsindexneighbourweightcandidatecandidate < distance[neighbour]Output
1
2
3
4
5
6
Written answer6 marks

Diagnose: (a) choosing the smallest single edge anywhere, (b) marking a node final when first discovered, and (c) applying standard Dijkstra with a negative edge.

Link each to the algorithm invariant.

Students type their answer here.

Independent transfer

Create your own five-node non-negative weighted graph with two competing routes. Produce a complete distance/predecessor table and verify the shortest route by summing its edges.

Written answer8 marks

Submit the edge list, table, route and verification.

Ensure at least one tentative distance is improved later.

Students type their answer here.

Closed-book checkpoint

Complete each sentence from memory. There is no answer bank and correctness is held for teacher review.

Fill in the blanks5 marks
An unsettled node's best known total is its completion 1 distance. Dijkstra finalises the unsettled node with the completion 2 value. Offering a lower cumulative route is edge completion 3. The route is reconstructed from completion 4, and standard Dijkstra requires completion 5 edge weights.

Review your understanding

Before submitting, check that you can explain the central distinction in your own words, expose the intermediate state that supports your answer and apply the method in an unfamiliar context.