Welcome to Network Algorithms!
In this chapter, we are going to explore how mathematics helps us find the most efficient ways to connect points or travel between them. Whether it’s Google Maps finding the fastest route to your friend's house or a utility company laying down fiber-optic cables for the least amount of money, Network Algorithms are working behind the scenes. This is part of the Discrete Mathematics section of your OCR Further Maths course.
Don't worry if this seems like a lot of steps at first. Think of these algorithms like recipes: if you follow the instructions step-by-step, you’ll get the right result every time!
1. Dijkstra’s Algorithm: Finding the Shortest Path
Imagine you are at home (Vertex A) and want to get to the cinema (Vertex G). There are many different roads and intersections in between. Dijkstra’s Algorithm is the tool we use to find the least weight path (the shortest distance, cheapest cost, or quickest time) between two specific vertices.
How it Works (The "Step-by-Step" Recipe)
1. Start at the beginning: Label your start vertex with a distance of 0. This is its permanent label.
2. Look at neighbors: For every vertex connected to your current vertex, calculate a temporary label by adding the edge weight to your current permanent label.
3. Update labels: If the new calculated distance is smaller than a previous temporary label, update it. If not, leave it alone.
4. Make it permanent: Look at all the temporary labels in the whole network. Pick the one with the smallest value and make it permanent. This is now your "current" vertex.
5. Repeat: Keep going until your destination vertex has a permanent label.
6. Trace back: To find the actual route, work backward from the destination, picking edges where the difference between permanent labels equals the edge weight.
Memory Aid: The Sat-Nav Rule
Dijkstra is like a greedy sat-nav. It always looks for the absolute shortest jump available next, ensuring that by the time you reach the end, you've taken the most efficient path possible.
Complexity and Efficiency
In your exam, you need to know that Dijkstra’s algorithm has quadratic order. In "Big O" notation, this is written as \(O(n^2)\), where \(n\) is the number of vertices. This means if you double the number of vertices, the time it takes to solve will roughly quadruple!
Quick Review: Dijkstra finds the shortest path between two specific points.
2. Minimum Spanning Trees (MST)
Sometimes, we don't want to go from A to B; we want to connect every single point in the network together for the minimum possible cost. This is called a Minimum Spanning Tree.
Important Term: A Tree is a graph with no cycles (no loops). A Spanning Tree connects every vertex.
Kruskal’s Algorithm
Kruskal’s is often the easiest to do by hand if you have a list of all the edges. It’s like building a railway system by buying the cheapest tracks first, no matter where they are on the map.
1. Sort: List all edges in order from smallest weight to largest.
2. Select: Pick the smallest edge.
3. Check for Cycles: Add the edge to your tree *unless* it creates a loop (a cycle). If it makes a loop, throw it away!
4. Repeat: Keep picking the next smallest edge until every vertex is connected.
Prim’s Algorithm
Prim’s is different because it "grows" the tree from a starting seed. You can do this on a diagram or using a distance matrix (table).
The Graphical Method:
1. Pick any vertex to start.
2. Look at all edges connecting your "grown" tree to "new" vertices. Pick the shortest one.
3. Repeat until everyone is invited to the party!
The Tabular (Matrix) Method:
1. Pick a starting column (usually A) and delete the row for A.
2. Label column A with a "1".
3. Look at all the numbers in the labeled columns. Circle the smallest available value.
4. The row of that value tells you the next vertex to add. Label its column with the next number (2, 3, etc.) and delete its row.
5. Repeat until all vertices are labeled.
Did you know?
While Kruskal’s and Prim’s look different, they will always give you the same total minimum weight for the tree!
Complexity and Efficiency
Both Prim’s and Kruskal’s algorithms have cubic order, written as \(O(n^3)\). They are slightly "heavier" for a computer to process than Dijkstra’s as the network grows very large.
Key Takeaway: Use Prim’s or Kruskal’s when you need to connect everything at minimum cost (e.g., electricity grids).
3. Choosing the Right Algorithm
A common challenge in Further Maths is deciding which "tool" to use for the job. Here is a quick guide:
Use Dijkstra if...
- The question asks for the "shortest route" from A to B.
- You need the "minimum time" or "least cost" between two specific places.
Use Prim’s or Kruskal’s if...
- The question asks for a "minimum connector."
- You need to "link all vertices" so that there is a path between any two.
- You want the "minimum total length" of a network.
Common Pitfalls to Avoid:
1. Cycles in Kruskal’s: Students often forget to check if an edge creates a loop. If you can get from A back to A without retracing your steps, you've made a cycle! Stop and reject that edge.
2. Updating Dijkstra: When calculating temporary labels, always add the edge weight to the permanent label of the vertex you just came from, not the previous temporary label.
3. Matrix Method: In Prim's tabular method, remember to delete the row of the vertex you just added to the tree so you don't accidentally pick it again.
Chapter Summary
1. Dijkstra’s Algorithm: Finds the shortest path between two points. It is \(O(n^2)\) (quadratic).
2. Kruskal’s Algorithm: Finds the Minimum Spanning Tree by picking the smallest edges and avoiding cycles. It is \(O(n^3)\) (cubic).
3. Prim’s Algorithm: Finds the Minimum Spanning Tree by growing it from a starting vertex. It can be done on a graph or a matrix. It is \(O(n^3)\) (cubic).
4. Modeling: Real-world problems (like one-way streets or broken bridges) can be modeled by adjusting the weights or directions (arcs) in these networks.
Great job! You've just covered the core logic behind modern logistics and networking. Keep practicing the "tracing" of these algorithms, and you'll find they become second nature!