A Level Computer Science 9618: A* Algorithm vs Dijkstra's Algorithm

A ride-hailing app models the road network of a district as a graph: junctions are nodes, and roads are edges weighted with the typical drive time, in minutes, between two junctions. A driver currently at junction S needs the fastest route to a single passenger waiting at junction G. The app can search this graph using either Dijkstra's algorithm or the A* algorithm.

(a) Describe one key difference between how Dijkstra's algorithm and the A* algorithm decide which node to explore next when searching a graph. [2]

(b) Explain why, for this single-destination journey from S to G, the A* algorithm would typically need to explore fewer junctions than Dijkstra's algorithm before finding the driver's route. [2]

(c) The app also has a separate feature that must work out the fastest drive time from junction S to every other junction in the district, not just one destination. State one reason why Dijkstra's algorithm may be more suitable than A* for this separate feature. [2]

Part (a): Key difference in node selection

Dijkstra’s algorithm chooses which node to explore next based only on the actual cumulative cost (drive time) travelled so far from the start node S. It has no information about where the goal G is, so it explores outward from S in every direction, based purely on cost so far.

The A* algorithm also uses this actual cost so far, but additionally adds a heuristic estimate of the remaining distance/time from that node to the goal G. It then explores the node with the smallest combined total (cost so far plus the heuristic estimate to the goal), making its search aim directly towards G rather than spread out evenly in every direction.

[2 marks]: [1] for stating that Dijkstra’s algorithm uses only the actual cost travelled so far, [1] for stating that A* additionally uses a heuristic estimate of the remaining distance to the specific goal.

Part (b): Why A* explores fewer junctions here

Because A* is goal-directed, its heuristic estimate constantly points the search towards G, it prioritises exploring junctions that appear to lie on the way to G, and tends to avoid spending time exploring junctions that lead away from G.

Dijkstra’s algorithm has no such guidance towards a specific goal, so it explores outward from S uniformly in every direction based on cost alone, until it happens to reach G, including many junctions that are nowhere near G and are irrelevant to this particular journey.

For a single, known destination like this one, A*‘s heuristic therefore lets it “home in” on G while typically exploring fewer irrelevant junctions than Dijkstra’s algorithm needs to.

[2 marks]: [1] for identifying that A*‘s heuristic focuses its search towards the specific goal G, [1] for explaining that Dijkstra’s algorithm instead explores outward in every direction with no bias towards G, so it typically checks more junctions before reaching it.

Part (c): Why Dijkstra’s algorithm suits the “distance to everywhere” feature

Dijkstra’s algorithm works out the shortest drive time from S to every junction it settles during a single run, since it explores outward from S based on cost alone rather than being aimed at one goal. This gives the shortest drive time from S to every junction in the district in one pass.

A*‘s heuristic estimate is defined relative to one specific goal junction at a time, so it is tuned to reach that one destination efficiently. It does not, in that same run, also guarantee the shortest drive time to every other junction in the district.

[2 marks]: [1] for stating that Dijkstra’s algorithm finds the shortest time from S to all junctions in one run, [1] for stating that A*‘s heuristic is instead tuned to one specific goal at a time, rather than every junction.

Final answers

(a) Dijkstra’s algorithm uses only actual cost so far; A* additionally uses a heuristic estimate of the remaining distance to a specific goal
(b) A*‘s heuristic focuses the search towards G, so it explores fewer irrelevant junctions than Dijkstra’s algorithm, which searches outward in every direction
(c) Dijkstra’s algorithm finds the shortest time from S to every junction in one run; A*‘s heuristic is tuned to one specific goal at a time