Dijkstra's algorithm

The boxes

Each vertex gets a box with three parts: the order in which it got its final value, the final value (shortest distance from the start), and working values (temporary distances, written in the order found).

The algorithm

1. Give the start vertex order 1 and final value 0.

2. For each vertex Y joined to the vertex X just given a final value, the working value is (final value of X) + (weight XY). Write it only if it is smaller than Y's current working value.

3. Of all vertices without final values, choose the one with the smallest working value; give it the next order number and make that value final.

4. Repeat until the destination (or every vertex) has a final value.

Finding the route

Trace back from the end: an edge XY is on the shortest route if final(Y) - final(X) = weight XY. Work back to the start, then write the route forwards.

Common slips

Write working values in order and do not cross them out. Continue the algorithm properly even if the answer looks obvious. Do not confuse Dijkstra with the forward pass of critical path analysis, which takes the largest value.

Worked example

Use Dijkstra's algorithm on network N to find the shortest route from A to G.

1. Order of final values: A 0, C 5, B 7, D 13, E 16, F 19, G 27
2. Working values: B: 7; C: 5; D: 14, 13; E: 17, 16; F: 23, 19; G: 29, 27
3. Trace back from G: G 27 - FG 8 = 19 = F; F 19 - EF 3 = 16 = E; E 16 - BE 9 = 7 = B; B 7 - AB 7 = 0 = A

Answer: Shortest route ABEFG, length 27

Check yourself

1. Use Dijkstra's algorithm to find the length of the shortest route from A to G in network N.
   Show answer

   27. Final values: A 0, C 5, B 7, D 13, E 16, F 19, G 27.

2. What is the shortest route from A to G in network N?
   • ACDEFG
   • ACEG
   • ABEFG
   • ADFG
   Show answer

   ABEFG. Tracing back from G gives ABEFG, length 27.

3. In Dijkstra's algorithm on network N from A, which vertex receives the 4th final value?
   • D
   • E
   • C
   • F
   Show answer

   D. The order is A, C, B, D, E, F, G.

4. In Dijkstra's algorithm on network N from A, what working values does F receive, in order?
   • 19
   • 19, 23
   • 22, 19, 27
   • 23, 19
   Show answer

   23, 19. From D (final 13): 13 + 10 = 23. From E (final 16): 16 + 3 = 19, which is smaller, so it is written too.

5. Use Dijkstra's algorithm starting at G to find the shortest distance from G to A in network N.
   Show answer

   27. Shortest distances are the same in both directions in an undirected network: the route is reversed.

6. When tracing back the shortest route, which test shows edge XY lies on it?
   • XY is the shortest edge at Y
   • X has the smaller order number
   • The working value at Y is the same as the weight of XY
   • final value of Y minus final value of X equals the weight of XY
   Show answer

   final value of Y minus final value of X equals the weight of XY. If final(Y) = final(X) + weight XY, then the shortest route to Y can come through X.

7. How does Dijkstra's algorithm decide which vertex gets the next final value?
   • The vertex joined to the start by the shortest edge
   • The vertex with the smallest working value among those not yet final
   • The vertex with the largest working value
   • The next vertex in alphabetical order
   Show answer

   The vertex with the smallest working value among those not yet final. Choosing the smallest working value guarantees that value cannot be improved later (weights are not negative).

Practise with instant feedback Print this lesson

Sources

• Pearson Edexcel International Advanced Level in Mathematics specification (issue 3)
• Pearson Edexcel IAL Decision Mathematics 1 scheme of work

Last updated 7 November 2026. Spotted a mistake? Tell us.