MskProdComputing
Back to the topic

The mark scheme starts on a new page, so you can print pages one and two for a student and keep the last page yourself. Everything prints in black on white whichever theme you are using.

Python · A Level 10

Dijkstra's Algorithm and A* Search

Section A: 10 multiple choice questions, 10 marks. Section B: 5 written questions, 19 marks. Total 29 marks.

Name

Class

Date

Mark  / 29

Section A

Circle the letter of the correct answer. One mark each.

  1. 1What does Dijkstra's algorithm find?1
    1. AThe order in which the vertices were added to the graph
    2. BThe vertex with the most edges in an unweighted graph
    3. CThe shortest path through a graph that has negative weights
    4. DThe shortest distance from a start vertex to every other vertex in a weighted graph
  2. 2Which data structure is used to choose the next vertex in Dijkstra's algorithm?1
    1. AA priority queue
    2. BA binary tree that is sorted by name
    3. CAn adjacency matrix
    4. DA stack
  3. 3What distance does Dijkstra's algorithm give every vertex except the start at the beginning?1
    1. AThe weight of its nearest edge
    2. BOne
    3. CInfinity
    4. DZero
  4. 4Why can Dijkstra's algorithm not be used on a graph with negative weights?1
    1. AThe graph would no longer be connected
    2. BThe algorithm would not be able to find the start vertex
    3. CA negative weight cannot be stored in a priority queue
    4. DA vertex that has been fixed could later be reached by a shorter route
  5. 5In A* search, what does f(n) = g(n) + h(n) represent?1
    1. AThe number of edges leaving vertex n
    2. BThe estimated total cost of a route that goes through vertex n
    3. CThe difference between the start and the goal
    4. DThe real distance from vertex n to the goal
  6. 6What does g(n) represent in A* search?1
    1. AThe cost of the best route found so far from the start to n
    2. BThe greatest edge weight in the graph
    3. CThe number of vertices adjacent to n
    4. DThe estimated cost from n to the goal
  7. 7What is an admissible heuristic?1
    1. AOne that has been approved by the user of the program
    2. BOne that never overestimates the true cost to reach the goal
    3. COne that is always exactly equal to the true cost
    4. DOne that gives the same estimate for every vertex
  8. 8Which heuristic suits a grid where movement is up, down, left or right only?1
    1. AThe number of cells already expanded
    2. BThe cost of the cell nearest the start
    3. CThe Manhattan distance to the goal
    4. DThe number of walls on the grid
  9. 9What is A* search when the heuristic is zero for every vertex?1
    1. AThe same as a linear search
    2. BThe same as a depth first search
    3. CThe same as Dijkstra's algorithm
    4. DIt does not work at all
  10. 10Why is A* often faster than Dijkstra's algorithm for finding a route to one particular place?1
    1. AIt avoids using a priority queue, which is the slowest part of Dijkstra's algorithm
    2. BIt stops checking the edge weights, so each step takes much less time
    3. CIt stores the whole graph as an adjacency matrix, which is faster to search
    4. DThe heuristic makes it explore mainly in the direction of the goal

Section B

Answer in the space provided. The number of marks tells you how many separate points to make.

  1. 1StateState the purpose of Dijkstra's shortest path algorithm, and state one restriction on the graph it is used on.2
  2. 2ShowUse Dijkstra's algorithm to find the shortest path from A to E in the graph shown. Show your working, and state the path and its total weight.6
    EdgeWeight
    A to B4
    A to C2
    B to C1
    B to D5
    C to D8
    C to E10
    D to E2
  3. 3CalculateIn an A* search, four vertices are waiting to be expanded. Their values of g and h are shown. Calculate f for each vertex and state which vertex is expanded next.3
    Vertexgh
    P46
    Q72
    R39
    S55
  4. 4ExplainExplain the role of the heuristic in the A* algorithm, and why it must not overestimate the cost.4
  5. 5CompareA satellite navigation system must find a route between two towns on a road network. Compare using Dijkstra's algorithm with using A* for this task.4

Mark scheme

Section A

1D2A3C4D5B6A7B8C9C10D

Section B

1 State the purpose of Dijkstra's shortest path algorithm, and state one restriction on the graph it is used on. 2

One mark for each of the following, to a maximum of 2.

  • It finds the shortest path, or the shortest distance, from a start vertex to the other vertices of a weighted graph
  • The weights must not be negative

Model answer. Dijkstra's algorithm finds the shortest path, meaning the one with the lowest total weight, from a start vertex to the other vertices of a weighted graph. It can only be used if none of the edge weights is negative.

2 Use Dijkstra's algorithm to find the shortest path from A to E in the graph shown. Show your working, and state the path and its total weight. 6

One mark for each of the following, to a maximum of 6.

  • A is given 0, and B and C are updated to 4 and 2 after A is fixed
  • C is fixed next, being the smallest, and B is improved to 3
  • B is fixed and D is updated to 8
  • D is fixed and E is updated to 10
  • The shortest path is A, C, B, D, E
  • The total weight is 10

Model answer. A is fixed at 0, which sets B to 4 and C to 2. C has the smallest distance so it is fixed next. The route to B through C is 2 + 1 = 3, which is less than 4, so B becomes 3. C also sets D to 10 and E to 12. B is fixed next at 3, and D becomes 3 + 5 = 8, which is less than 10. D is fixed at 8, and E becomes 8 + 2 = 10, which is less than 12. E is fixed at 10. Reading back from E, it was reached from D, D from B, B from C and C from A. The shortest path is A, C, B, D, E and its total weight is 10.

3 In an A* search, four vertices are waiting to be expanded. Their values of g and h are shown. Calculate f for each vertex and state which vertex is expanded next. 3

One mark for each of the following, to a maximum of 3.

  • f is calculated as g + h
  • The values are P = 10, Q = 9, R = 12 and S = 10
  • Q is expanded next, as it has the lowest f

Model answer. f is g plus h, so P is 4 + 6 = 10, Q is 7 + 2 = 9, R is 3 + 9 = 12 and S is 5 + 5 = 10. The vertex with the lowest value of f is expanded next, which is Q.

4 Explain the role of the heuristic in the A* algorithm, and why it must not overestimate the cost. 4

One mark for each of the following, to a maximum of 4.

  • The heuristic is an estimate of the cost from a vertex to the goal
  • It is used to choose the vertex to expand next, so the search is guided towards the goal
  • This means fewer vertices are explored than in Dijkstra's algorithm
  • If it overestimated, a vertex on the shortest path could be made to look too costly and be ignored, so the path found might not be the shortest

Model answer. The heuristic is an estimate of the cost of getting from a vertex to the goal. A* adds it to the cost so far and expands the vertex with the lowest total, which guides the search towards the goal, so it explores fewer vertices than Dijkstra's algorithm, which spreads out in every direction. It must not overestimate because a vertex on the shortest path could then look more expensive than it really is, and be passed over, so the path found might not be the shortest.

5 A satellite navigation system must find a route between two towns on a road network. Compare using Dijkstra's algorithm with using A* for this task. 4

One mark for each of the following, to a maximum of 4.

  • Both find the shortest route if the weights are not negative and the heuristic is admissible
  • Dijkstra's explores in every direction from the start, including roads that lead away from the destination
  • A* uses an estimate, such as the straight line distance to the destination, to explore mainly towards it
  • So A* usually finds the route more quickly, and is better for this task, though it needs a suitable heuristic

Model answer. Both algorithms find the shortest route, provided the road lengths are not negative and the heuristic used by A* never overestimates. Dijkstra's algorithm explores outwards in every direction from the start, including roads leading away from the destination. A* uses an estimate, such as the straight line distance to the destination, to explore mainly towards it. A* is therefore usually quicker for finding a route between two particular towns, and the better choice here, although it needs a suitable heuristic to be available.