Dijkstra's algorithm

Dijkstra's algorithm

Spec 2.2 · Edexcel International A Level Maths: Revision notes

Studying this course? Keep your progress in one place.

Key facts

  • Dijkstra's algorithm finds the shortest distance from a start vertex to every vertex of a network with positive weights.
  • Each vertex has a box with the order of labelling, the final value and the working values.
  • A new working value is the final value of the vertex just labelled plus the arc weight; keep it only if it is smaller.
  • Find the route by back-tracking: final value of vertex − arc weight = final value of the previous vertex.
  • You can stop as soon as the target is permanently labelled.

The shortest path problem

The shortest path problem asks for the path between two vertices with the least total weight. Dijkstra's algorithm solves it by labelling vertices in order of increasing distance.

In a network each arc has a weight, such as a distance, time or cost. The shortest path problem asks for the path between two vertices of least total weight.

Trying every path becomes impractical as the network grows, so we use Dijkstra's algorithm.

It works from a start vertex, finds the shortest distance to every vertex, and works for any network with positive weights. It can stop once the target is permanently labelled.

w=4w=2w=1w=6w=8SABT
The network used in the worked example

When can you stop Dijkstra's algorithm if you only need the distance to one target vertex?

The algorithm step by step

Label the start vertex 0, update the working values of its neighbours, make the smallest working value permanent, and repeat until the target is labelled.

Give each vertex a box with three parts: the order of labelling, the final value and the working values.

Working values that are replaced by smaller ones are crossed out but kept, so the working can be checked.

  1. 1

    Start

    give the start vertex order 1 and final value 0

  2. 2

    Update neighbours

    final value + arc weight; keep it if smaller than the working value there

  3. 3

    Choose

    take the smallest working value not yet permanent; make it final and give it the next order number

  4. 4

    Repeat

    update and choose until the target is labelled

One round of Dijkstra's algorithm
  • New working valuefinal value just labelled + arc weight

Which value do you add the arc weight to when updating a neighbouring vertex?

Worked example

Starting at S, B becomes permanent at 2, then A at 3 by going via B, then T at 9.

Take the network above with arcs SA=4SA=4, SB=2SB=2, AB=1AB=1, AT=6AT=6 and BT=8BT=8.

Work through the labelling in order. The working value A=4A=4 is replaced by 3 when a shorter route via BB is found, and T=10T=10 is replaced by 9 via AA.

  1. 1

    S = 0 (order 1)

    the start

  2. 2

    B = 2 (order 2)

    the smallest working value after S

  3. 3

    A = 3 (order 3)

    via B: 2 + 1 = 3, replacing 4

  4. 4

    T = 9 (order 4)

    via A: 3 + 6 = 9, replacing 10

Order in which vertices become permanent in the worked example

S

Order of labelling:
1
Final value:
0
Working values:
none

B

Order of labelling:
2
Final value:
2
Working values:
2

A

Order of labelling:
3
Final value:
3
Working values:
4, 3

T

Order of labelling:
4
Final value:
9
Working values:
10, 9
The labelled network

Worked example

Use Dijkstra's algorithm to find the shortest distance from SS to TT.

In the example, why is A=4A=4 replaced by 33?

Finding the route

Work backwards from the target: move to a neighbour whose final value equals the vertex's final value minus the arc weight.

The final values give the length, but you must also give the route. Work backwards from the target. At each vertex, choose the neighbour for which the final value of the vertex minus the arc weight equals the final value of the neighbour.

Write the route from the start to the target, with its total length.

  1. 1

    T = 9

    9 − 6 = 3 = A, so go to A

  2. 2

    A = 3

    3 − 1 = 2 = B, so go to B

  3. 3

    B = 2

    2 − 2 = 0 = S, so the start is reached

Backtracking from T to find the route
  • Final value of vertex − arc weight= final value of neighbour

Back-tracking in the worked example

Find the route from SS to TT.

A vertex VV has final value 1111 and is joined to WW by an arc of weight 44. WW has final value 77. Is WW on the shortest route to VV?

Updating and checking

If a road closes, remove the arc and repeat. A new arc of weight xx helps only if d(S,X)+x+d(Y,T)d(S,X)+x+d(Y,T) is less than the current shortest length.

If a road is closed, remove that arc and repeat the algorithm. Any vertex whose shortest route did not use that arc keeps its final value.

If a new arc of weight xx joins XX and YY, it improves the route only when the new total is less than the current shortest length. Here dd is the shortest distance, found from the algorithm. This gives an inequality for xx.

Checks: final values increase in order of labelling.

0123456789101112current shortest = 9
  • New arc xx improves route whend(S,X)+x+d(Y,T)<d(S,X)+x+d(Y,T)< current length

In the worked example the shortest length is 99. A new arc of weight xx joins SS directly to TT. For what values of xx is the shortest route improved?

Try an exam question

A network has arcs SA = 6, SB = 4, AB = 1, AT = 9, BC = 7 and CT = 2. Use Dijkstra's algorithm to find the shortest route from S to T and state its length.

[4 marks]

That's the notes covered.

Carry on to the next subtopic.

Try a question

Which vertex is permanently labelled third, counting SS as the first?

1 mark, marked against the mark scheme

Revision notes