Calculate the shortest distance between the base and each of the other towns in the diagram using Dijkstra's algorithm. Show your working and write your answers in the table provided. [Figure X.X] Answers Town 1 Town 2 Town 3 Town 4 Town 5 Town 6

Mark scheme

Marking points from the official mark scheme (May/June 2021). The mark or mark type is shown in brackets.

1. [1] (a) Initialisation: setting Base to 0 and other towns to infinity
2. [1] (a) Evidence of values at nodes being updated (e.g., showing paths and intermediate distances)
3. [1] (a) Evidence of 'visited node(s)' (e.g., marking nodes as visited)
4. [1] (a) At least four correct shortest distances
5. [1] (a) All shortest distances correct: Town 1: 3, Town 2: 5, Town 3: 2, Town 4: 9, Town 5: 3, Town 6: 8
6. [1] (b) Artificial Neural Networks can be represented using graphs
7. [1] (b) Graphs provide structures for relationships // graphs provide relationships between nodes
8. [1] (b) AI problems can be defined/solved as finding a path in a graph
9. [1] (b) Graphs may be analysed/ingested by a range of algorithms
10. [1] (b) ...e.g. A* / Dijksta's algorithm
11. [1] (b) ...used in machine learning.
12. [1] (b) Example of method e.g. Back propagation of errors / regression methods