Shortest path

In a weighted graph or network, travelling becomes more complex as optimising resources, such as time or cost, must be considered. This is where finding the shortest path plays a critical role in determining the most efficient route between vertices.

Finding Shortest Path

Finding the shortest path in a network can sometimes be done by inspection, particularly when the network is simple. However, as the complexity of the network increases, a more systematic approach is required. One such method is Dijkstra's algorithm, which efficiently identifies the shortest path between vertices.

Dijkstra’s Algorithm

Dijkstra’s algorithm is a method of finding the shortest path. The steps involved are:

1. Assign a starting value of \(0\) to the starting vertex.
2. Compare the distance from the starting vertex to all unvisited neighbouring vertices, and next to each of these vertices calculate the value required to reach it from the value of the visited vertex.
3. Mark the lowest calculation out of all the unvisited neighbouring vertices as visited. This can be done by drawing a box around the visited vertex.
4. From the newly visited vertex, calculate the value required to reach the unvisited neighbouring vertices.
   1. If the calculation is less than the previous value, then update the value to that vertex
   2. If the calculation is more than the previous value, then leave the previous value on the vertex.
5. Repeat steps 3 and 4 until the end vertex is visited.
6. Backtrack from the end vertex to the start to determine the shortest path.

Back Next