Dijkstra's Algorithm (Edexcel A Level Further Maths: Decision Maths 1)

What is Dijkstra's algorithm?

• Dijkstra's algorithm is used to find the shortest distance between two vertices in a network
  • More precisely, if the algorithm is applied to a whole network it will find the shortest distance between a (fixed) start vertex and every other vertex
  • However, if the destination (end) vertex is reached before the entire network has been considered the algorithm can stop
    • This would be useful, say, in a larger network as it would reduce the time for the algorithm to complete
• It can be used in practical applications to reduce time, cost or distance between two points
• Fun fact ...
  
  • ... a version of Dijkstra's algorithm was used in the Pacman video game to control the movement of the ghosts that chased Pacman!

What notation is used in Dijkstra's algorithm?

• Each vertex will be given a labelling box

• • Values in the 'Vertex' box are simply the label of the vertex
  • The value in the 'Labelling order' box is the vertex's place in the order of being assigned a value in its 'Final label' box
  • The value in the 'Final label' box is the shortest distance of the vertex from the start vertex
    • 'Final label' is sometimes referred to as 'permanent label'
  • The most recently written value in the 'Working values' box is the current distance of the vertex from the start vertex, the final value in this box will be the same as the value in the 'Final label' box

What are the steps of Dijkstra's algorithm?

• STEP 1
  Draw a labelling box for each vertex in the network (if not already given) and complete the 'Vertex' box for each vertex
   
• STEP 2 
  Complete the labelling box for the start vertex:
  • Put '1' in the 'Order of labelling' box
  • Put '0' in the 'Final label' box
     
• STEP 3
  Inspect all vertices that are connected by an edge to the vertex that has most recently had its 'Final label' box completed
  
  • This only applies to vertices that do not already have a completed 'Final label' box

   Put a working value in the relevant box for each of these vertices

• • The working value should be the sum of the value in the 'Final label' box of the vertex whose final label was most recently completed and the length of the edge connecting the vertices
  • If there is already a working value, only replace it if the new working value is smaller

• STEP 4
  Look at all vertices with a value in the 'Working value' box (ignoring vertices which have their 'Final label' box completed)
  Identify the vertex with the smallest working value and complete its labelling box:
  • Put the next sequential number in the 'Order of labelling' box
  • Put the current working value into its 'Final label' box
     
• STEP 5
  Repeat steps 3 and 4 until the end vertex has its 'Final label' box completed
  • (or until every vertex has a final label)
     
• STEP 6
  Move backwards from the destination (end) vertex towards the start vertex to identify the shortest path
  Two vertices lie on the shortest path if the difference between the values in their 'Final label' boxes is equal to the weight of the arc that connects them