Dijkstra's algorithm is used to find the shortest path.
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.
- Box the start node by labelling it with a one in Box A and zero in Box B.
- 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.
- 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.
- 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.)
- Repeat 3 and 4 until the destination node has a permanent label.
- Go backwards through the network retracing the path of shortest length to the start node.
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 n2 so it is efficient enough to use for relatively large problems.
- Dijkstra's algorithm does not work with negative weight arcs.
See the other D1 notes:
- Sorting algorithms
- Packing algorithms
- Graphs and networks
- Minimum connector problems
- The shortest path
- Route inspection
- The travelling salesman problem
- Linear programming
- The simplex algorithm