• Tweet

• 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

Advantages of Dijkstra

• 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 n² so it is efficient enough to use for relatively large problems.

Disadvantages

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

Also See

See the other D1 notes:

1. Algorithms
2. Sorting algorithms
3. Packing algorithms
4. Graphs and networks
5. Minimum connector problems
6. The shortest path
7. Route inspection
8. The travelling salesman problem
9. Linear programming
10. The simplex algorithm

Comments