• # Revision:The Shortest Path

TSR Wiki > Study Help > Subjects and Revision > Revision Notes > Mathematics > The Shortest Path

Dijkstra's algorithm is used to find the shortest path.

## Labelling nodes

When performing Dijkstra's algorithm, the nodes are labelled in a certain way.

• Box A shows the order in which the node was made permanent. I.e. the first node to be made permanent will be labelled with a 1, and so on.
• Box B shows the shortest length possible to get to that node.
• Box C is the box showing temporary labels.

## Algorithm

1. Box the start node by labelling it with a one in Box A and zero in Box B.
2. Consider the nodes connected to the start node. Temporarily label these (in Box C) with the weight of the arc connecting the node to the start node.
3. Look at the temporary labels of all nodes which have not yet been boxed. Make the node with the smallest temporary label permanent by copying the value in Box C to Box B. Also fill in Box A.
4. Consider the nodes connected to the most recently boxed node. Temporarily label these in Box C with the value of the boxed node plus the weight of the arc connecting the node to the boxed node. (If the node has already got a value in Box C which is bigger than the value you just worked out, cross it out and replace it with your new, smaller value.)
5. Repeat 3 and 4 until the destination node has a permanent label.
6. Go backwards through the network retracing the path of shortest length to the start node.

## Example

• Once it has been carried out you can find the least weight path to all permanently labelled nodes.
• You don't need a new diagram for each pass.
• Dijkstra's algorithm has an order of n2 so it is efficient enough to use for relatively large problems.

• Dijkstra's algorithm does not work with negative weight arcs.

## Also See

See the other D1 notes:

Try Learn together, TSR's study area

35,184
revision notes

38,559
mindmaps

38,639
crosswords

15,072
quizzes

create
a study planner

thousands
of discussions

Today on TSR

### Who is getting a uni offer this half term?

Find out which unis are hot off the mark here

### How to get a 1st class degree

Poll
Study resources

The Student Room, Get Revising and Marked by Teachers are trading names of The Student Room Group Ltd.

Register Number: 04666380 (England and Wales), VAT No. 806 8067 22 Registered Office: International House, Queens Road, Brighton, BN1 3XE