Dijkstra Algorithm (Leaving Cert Applied Maths): Revision Notes
Dijkstra's Algorithm
What is Dijkstra's algorithm?
Dijkstra's Algorithm is a systematic method used to find the shortest path from one node to another in a weighted graph or network. This powerful algorithm helps us determine the most efficient route between two points when multiple paths are available.
The term "shortest" can have different meanings depending on the context:
- Shortest distance - the physically shortest route
- Quickest time - the fastest route considering speed limits
- Lowest cost - the cheapest route considering tolls or fuel costs
The algorithm works by examining the weights (numbers) assigned to the edges connecting the nodes in the graph.
Purpose and real-world applications
Dijkstra's Algorithm has many practical applications in everyday life:
- GPS navigation systems use this algorithm to calculate the shortest routes between locations
- Network routing in computer systems to find the most efficient data paths
- Transportation planning to optimise delivery routes
- Emergency services to find the quickest routes to incidents
These applications demonstrate how the algorithm solves real-world problems by finding optimal paths in complex networks.
How the algorithm works
The systematic approach
The algorithm uses a structured table-based method to track progress. For each node in the network, we maintain important information that helps us find the optimal path.
Table format for tracking progress
Each node in our network has a corresponding table with three key components:
Table Components:
- Node: The letter or identifier for each vertex
- Order of labelling: The sequence in which we complete each node (1st, 2nd, 3rd, etc.)
- Final value: The shortest distance from the starting node
- Working values: Temporary calculations we update during the process
Step-by-step process
Core Algorithm Steps:
The algorithm follows a clear pattern that we repeat until all nodes are complete:
- Start with your chosen starting node and label it with order "1" and final value "0"
- Update working values for all nodes directly connected to the completed node
- Choose the node with the smallest working value among uncompleted nodes
- Make this node permanent by giving it the next order number and recording where it came from
- Repeat steps 2-4 until all nodes are completed
Key rule to remember: Always choose the node with the SMALLEST working value next.
Worked example walkthrough
Let's work through a complete example to find the shortest path from node S to node Z. This step-by-step demonstration will show how the algorithm systematically finds the optimal route.
Initial setup
Step 1: Starting the Algorithm
Step 1a: We start at node S, so we label it first with order "1" and final value "0" since the distance from S to itself is 0.
Step 1b: We fill in working values for nodes directly connected to S. In this case:
- T gets working value 12
- W gets working value 7
Step-by-step execution
Step 2: First Node Selection
Step 2a: Among the uncompleted nodes, W has the smallest working value (7), so we make W permanent as our second completed node.
Step 2b: Now we update working values for any node that W connects to in one step. This includes T, U, and X:
- T: We can reach it from W in , which is better than the current 12
- U: W connects to U in 9 steps, so
- X: W connects to X in 8 steps, so
Step 3: Continuing the Process
Step 3a: Looking at all uncompleted working values, T has the smallest (10), so T becomes our third completed node.
Step 3b: We update the working value for any node connected to T. Only U is connected to T, and we can reach U from T in , which is better than the existing 16.
Step 4: Algorithm Progression
Step 4a: Among remaining nodes, U now has the smallest working value (14), so U becomes our fourth completed node.
Step 4b: Updating working values for nodes connected to U gives us:
- V:
- X: (but this is larger than the existing 15, so we keep 15)
- Y:
Completing the algorithm
We continue this systematic process for the remaining nodes (X, V, Y, and finally Z), always selecting the node with the smallest working value.
The final completed state shows Z with a final value of 28, meaning the shortest distance from S to Z is 28.
Tracing the shortest path
Finding the Actual Path:
To find the actual shortest path, we work backwards from Z, looking at which node each came from:
- Z came from V (shown as 28, 30(V))
- V came from U (shown as 20(U))
- U came from T (shown as 16, 14(T))
- T came from W (shown as 12, 10(W))
- W came from S (shown as 7(S))
Therefore, the shortest path is: S → W → T → U → V → Z with a total distance of 28.
Key Points to Remember:
-
Dijkstra's Algorithm finds the shortest path between nodes in a weighted network by systematically examining all possible routes
-
Always choose the node with the smallest working value when deciding which node to complete next
-
Keep track of where each node came from so you can trace back the actual shortest path at the end
-
The algorithm has real-world applications in GPS systems, computer networks, and transportation planning
-
Update working values for adjacent nodes each time you complete a new node, always keeping the smallest value when multiple paths exist