Welcome to Optimisation Algorithms!
Hi there! Have you ever wondered how Google Maps magically finds the quickest route home during rush hour? Or how a data packet finds its way across the massive maze of the internet to reach your computer?
In this chapter, we are diving into Optimisation Algorithms. Specifically, we will look at Dijkstra’s Shortest Path Algorithm. "Optimisation" simply means finding the best or most efficient way to do something. In computer science, that usually means finding the shortest distance, the lowest cost, or the fastest time.
Don’t worry if this seems a bit technical at first—we’ll break it down step-by-step using simple analogies!
Prerequisite: What is a Graph?
Before we start, remember that Dijkstra’s algorithm works on a weighted graph.
1. Nodes (or Vertices): The "stops" or points on the map (like cities or routers).
2. Edges (or Arcs): The paths connecting those stops (like roads or cables).
3. Weights: The numbers on the edges. These represent the "cost" of the path (like distance, time, or money).
Dijkstra’s Shortest Path Algorithm
Dijkstra’s algorithm is a famous method used to find the shortest path from one specific starting node to all other nodes in a weighted graph.
Think of it like this: You are standing at a "Start" node. You want to reach a "Destination" node. The algorithm methodically explores the paths, always keeping track of the shortest distance found so far to every single "stop" on the map.
An Everyday Analogy: The Stepping Stones
Imagine you are trying to cross a pond using stepping stones. Each stone has a number representing how slippery it is (the weight). You want to reach the other side with the lowest total slipperiness score.
Dijkstra’s is like a very cautious person who looks at all the stones they can reach from their current spot, writes down the total slipperiness to get there, and then always moves to the stone that currently has the lowest total score recorded. They keep updating their notes if they find a better way to a stone they've seen before.
How the Algorithm Works (The Tracing Logic)
The AQA syllabus doesn't require you to memorize the exact code, but you must be able to trace it (follow it step-by-step). Here is the logical flow:
1. Initialisation:
- Assign every node a distance value. Set the Start Node to 0 and all other nodes to Infinity \( (\infty) \).
- Mark all nodes as unvisited.
2. The Loop:
- Choose the unvisited node with the smallest distance. Let's call this the "Current Node."
- For the Current Node, look at all of its unvisited neighbors.
- Calculate their distance from the start through the Current Node.
- If this new distance is smaller than the distance currently recorded for that neighbor, update it!
3. Finishing Up:
- Once you have checked all neighbors of the Current Node, mark the Current Node as visited. A visited node is never checked again.
- Repeat the loop until all nodes are visited (or you reach your target).
Quick Review: Why use Infinity?
We set the initial distances to infinity because we don't know the path yet! It's a way of saying, "I haven't found a way here yet, so any path I find will definitely be better than this."
Tracing Dijkstra: A Simple Example
Imagine a graph with nodes A, B, and C.
- Edge A to B has weight 5.
- Edge B to C has weight 2.
- Edge A to C has weight 10.
If we start at A:
1. Step 1: Start node A = 0, B = \( \infty \), C = \( \infty \).
2. Step 2: Smallest unvisited is A. Neighbors are B (dist 5) and C (dist 10). Both are smaller than \( \infty \), so we update them.
- Distances: A=0, B=5, C=10. Mark A visited.
3. Step 3: Smallest unvisited is B (5). Neighbor is C.
- Distance to C through B is \( 5 + 2 = 7 \).
- Is 7 smaller than the current distance to C (10)? Yes! Update C to 7.
- Distances: A=0, B=5, C=7. Mark B visited.
4. Step 4: Only C is left. Mark it visited. The shortest path from A to C is 7.
Key Takeaway:
Dijkstra's is a "greedy" algorithm—at every step, it makes the choice that looks best right now (the smallest distance) to ensure it finds the mathematically perfect shortest path by the end.
Applications of Shortest Path Algorithms
In your exam, you might be asked where this is actually used. Here are the big ones:
1. Satellite Navigation Systems (GPS): Finding the shortest or fastest driving route between two locations.
2. Network Routing: On the internet, routers use Dijkstra-like algorithms to find the fastest way to send your data packets to their destination.
3. Social Networks: Suggesting "people you may know" by finding the shortest path of connections between users.
4. Logistics: Planning flight paths for airlines or delivery routes for courier companies to save fuel and time.
Did You Know?
Edsger Dijkstra, the computer scientist who created this, supposedly thought of the algorithm in just 20 minutes while sitting at a cafe with his fiancée! He didn't use a pen or paper; he just thought it through in his head because he wanted to prove how simple it could be.
Common Mistakes to Avoid
- Forgetting to add weights: When updating a neighbor, remember you must add the distance of the current node to the edge weight. Don't just look at the edge weight alone!
- Visiting the wrong node next: Always pick the node with the smallest total distance from the start, not just any neighbor.
- Updating to a larger number: Only update a node's distance if the new path you found is shorter than the one already written down.
Section Summary
Optimisation: Making an algorithm as efficient as possible (e.g., finding the shortest path).
Dijkstra’s Algorithm: Finds the shortest path from a start node to all other nodes in a weighted graph.
Greedy approach: It always picks the "cheapest" unvisited node to explore next.
Real-world use: GPS, internet routing, and logistics.
Don't worry if this seems tricky at first! The best way to master Dijkstra's is to grab a piece of paper, draw a few circles and lines with numbers, and try to trace the steps yourself. You'll be a pro in no time!