Dijkstra's algorithm

Dijkstra's algorithm

Spec 2.2 · Edexcel A-Level Further Maths: Revision notes

Studying this course? Keep your progress in one place.

Key facts

  • Dijkstra's algorithm finds the shortest path from a start vertex to every other vertex. Weights must not be negative.
  • Each vertex records its order of labelling, its final label and its working values.
  • The smallest working value among unlabelled vertices is made permanent and never changes.
  • Find the route by working backwards from the target: label plus edge length equals the label you are at.
  • For a route through a vertex, add the shortest distance to it and from it.

What Dijkstra's algorithm does

It finds the shortest distance from one start vertex to all other vertices of a network with non-negative weights.

Dijkstra's algorithm gives routes such as the shortest road distance or least travel time.

Each vertex is a box with four parts:

  • the vertex name,
  • the order of labelling: 1 for the start, 2 for the next vertex made permanent, and so on,
  • the final label: the shortest distance from the start,
  • the working values tried and replaced on the way.

A permanent label is fixed once the vertex is chosen.

  • Start vertexorder 1, final label 0
  • Permanent labelshortest distance, never changes

What order of labelling does the start vertex receive?

The steps

Label the start 0, update working values from the newest label, then make the smallest unlabelled working value permanent. Repeat.

  1. Give the start vertex permanent label 0 and order 1.
  2. For each vertex joined to the vertex just labelled, add its label to the edge length. If this is smaller than the current working value (or none exists), record it and cross out the larger one.
  3. Choose the smallest working value among vertices without a permanent label. Make it permanent and give the next order.
  4. Repeat steps 2 and 3 until the target (or every vertex) is labelled.

The smallest value is final because any other route must pass through a vertex with a value at least as large.

  1. 1

    Update

    add the label to each edge length and record smaller working values

  2. 2

    Choose

    pick the smallest working value among unlabelled vertices

  3. 3

    Make permanent

    give it the next order of labelling

Then back to step 1

Repeat until the target is labelled

Working values at unlabelled vertices are P=8P=8, Q=5Q=5, R=7R=7. Which is made permanent next?

A worked example

Work outwards from SS, always labelling the smallest working value, until TT is labelled.

Roads: SA=4SA=4, SB=7SB=7, AB=2AB=2, AC=6AC=6, BC=3BC=3, BD=8BD=8, CD=6CD=6, CT=8CT=8, DT=4DT=4. Find the shortest route from SS to TT.

The labels give the shortest distance to each vertex. Compare all working values at TT before stopping.

SA 4SB 7AB 2AC 6BC 3BD 8CD 6CT 8DT 4SABCDT
Solid edges form the shortest route S-A-B-C-T.

Worked example

Apply Dijkstra's algorithm from SS to TT.

Via DD the distance to TT is 14+414+4. What happens to this value?

Finding the route

Work backwards from the target: at each vertex pick the neighbour whose label plus the edge length equals the label there.

The labels give the length. To find the route, start at the target and find the neighbour whose final label plus the edge length equals the label you are at.

In the example, T=17=9+8T=17=9+8 so the route comes from CC. C=9=6+3C=9=6+3, so from BB. B=6=4+2B=6=4+2, so from AA, and A=4A=4 from SS.

The route is S−A−B−C−TS-A-B-C-T with length 17. Show these sums to justify each step.

For a directed network, only follow arcs in the direction of the arrow.

  • Label of earlier vertex edge length = label here

Final labels are S=0S=0, A=4A=4, B=6B=6, C=9C=9, D=14D=14, T=17T=17. Using the example network, which vertex comes just before DD on the shortest route to DD?

Variations

Final labels give every distance, a vertex to call at splits the problem in two, and a closed road means repeating from where it mattered.

The final labels give the shortest distance to every labelled vertex, not just the target.

A vertex's shortest route may leave a long edge unused, so compare all working values at the target before you stop.

Several targets

  • Read every final label

Route via X

  • Add start-to-X and X-to-target

Road closed

  • Redo from where it mattered

Directed

  • Follow arrows only

A route must call at XX. The shortest distance from the start to XX is 5 and from XX to the target is 9. What is the length of the shortest such route?

Try an exam question

A network has roads SA=3SA=3, SB=6SB=6, AB=2AB=2, AC=7AC=7, BC=3BC=3, BT=9BT=9, CT=4CT=4. Use Dijkstra's algorithm to find the shortest distance from SS to TT and state the route.

[5 marks]

That's the notes covered.

Carry on to the next subtopic.

Try a question

What is the final label of vertex BB?

1 mark, marked against the mark scheme

Revision notes