Welcome to Algorithms on Graphs II: Finding the Shortest Path!
Hello future Mathematicians! This chapter is incredibly practical and powerful. In Decision Mathematics 1 (D1), we move from simply drawing graphs to actually *using* them to solve real-world problems.
The main focus of this section is finding the shortest route between two points, or sometimes, between one point and *all* others. Think of this as the mathematics behind your GPS navigation system!
Unit D1 Focus: The Shortest Path Problem
We often deal with weighted graphs, where each arc (or edge) has a numerical value (the weight) representing distance, time, cost, or capacity. Our primary goal is to minimize the total weight along a path.
Did you know? Finding the shortest path is crucial in logistics, telecommunications (routing data packets), and even optimizing factory floor movement.
Dijkstra's Algorithm: The Shortest Path Finder
The most famous and reliable method for solving the shortest path problem (when weights are non-negative) is Dijkstra's Algorithm. It’s an efficient way to find the shortest path from a starting node (source) to every other node in the graph.
Prerequisite Check: Why Dijkstra's?
- It guarantees the shortest path will be found.
- It must only be used on graphs where all weights (distances/times) are non-negative (zero or positive).
Analogy: Imagine you are a postman starting at the depot (Node S). Dijkstra’s Algorithm is your systematic way of ensuring that every time you travel to a new area, you have taken the fastest or shortest possible route to get there.
Key Concepts: Labels, Labels, Labels!
Dijkstra’s Algorithm works by assigning labels to every node. Each label consists of two parts:
Label Notation: \( (L, P) \)
- L (Length/Value): The current shortest known distance from the start node to this node.
- P (Preceding Node): The node immediately before this node on the current shortest path found so far.
These labels exist in two states: Temporary or Permanent.
- Temporary Label: This is the current best guess for the shortest path length. It can be crossed out and updated if a shorter route is found.
- Permanent Label: Once we have established that the current length L is definitely the shortest possible distance to this node, the label becomes permanent (usually indicated by boxing the label). This node is now finalized, and we use it as a base for calculating paths to other temporary nodes.
Memory Aid: Think of the 'P' in Permanent. Once a path is Permanent, you Promise you won't change it!
Step-by-Step Guide to Dijkstra's Algorithm
Don't worry if this seems tricky at first. It's a mechanical process. If you follow these steps systematically, you will succeed!
Step 1: Initialization
- Set the starting node (Source node, S) label as Permanent: \( \mathbf{(0, -)} \). (Length 0, no preceding node).
- Set all other node labels as Temporary, usually \( (\infty, -) \) or just leave them blank initially.
Step 2: Scanning the Permanent Node
- Identify the most recently permanently labelled node (let’s call it Node X).
- Look at all the temporary nodes connected directly to Node X.
-
Calculate the potential new length to each adjacent temporary node (Y) using the formula:
Potential Length to Y = (Permanent Length of X) + (Weight of arc X to Y)
Step 3: Updating Temporary Labels (Scanning)
- For each temporary node (Y), compare the Potential New Length (calculated in Step 2) with its Current Temporary Length.
- If the Potential New Length is smaller than the current length, cross out the old temporary label and write the new, improved label \( (L_{new}, X) \).
Common Mistake Alert: Students often forget to cross out the old temporary label. Always update the label if you find a shorter route!
Step 4: Making a Label Permanent
- Once you have scanned Node X and updated all adjacent temporary labels, look at all currently temporary labels in the entire graph.
- Choose the temporary label that has the smallest length (L).
- Make this label Permanent (box it). This node is now the new Node X for the next iteration (Step 2).
Step 5: Stopping Condition
- Repeat Steps 2, 3, and 4 until all nodes have been permanently labelled.
Tracing Back the Shortest Path
Once the algorithm is complete, the shortest distance to any node is simply the length (L) in its permanent label. But how do you find the actual path?
You use the Preceding Node (P) part of the label and work backwards!
- Start at the destination node (T).
- Look at its permanent label \( (L_T, P_T) \). The shortest path came immediately from node \( P_T \).
- Move to node \( P_T \). Look at its label to find the node that came before it.
- Continue tracing backwards, node by node, until you reach the start node (S).
- Write the path in the correct forward order (S to T).
Example: If the final label at Node F is \((15, C)\), the path came from C. If C’s label is \((10, B)\), the path came from B. The path segment so far is S → ... → B → C → F.
Quick Review: Dijkstra's Checkpoints
Key Takeaway 1: The Permanent Box
The moment a label is boxed (made permanent), its length (L) is the definitive shortest distance from the start node. This distance will never change.
Key Takeaway 2: The Critical Choice
When deciding which temporary label to make permanent in Step 4, you must look at ALL temporary labels on the graph, not just the ones adjacent to the node you just scanned.
Key Takeaway 3: Path Recording
Always record the path by working backwards using the Preceding Node (P) and then presenting the final answer forwards.
Alternative Scenario: Finding the Shortest Path Between Two Specific Nodes
Sometimes, the exam only asks for the shortest path between Node A and Node B (not A to all nodes).
You still use Dijkstra's Algorithm, but you can stop the process as soon as Node B receives its permanent label. There is no need to make the remaining temporary nodes permanent, saving time in the exam!
A Note on Alternative Algorithms (TSP - Bounds)
While Dijkstra's solves the shortest path for a single source, you may encounter questions related to the Travelling Salesperson Problem (TSP), which asks for the shortest tour that visits every node exactly once and returns to the start.
The D1 curriculum does not require you to solve the TSP, which is computationally difficult. Instead, you need to be able to find bounds for the solution:
Lower Bound for TSP
The standard method for finding a lower bound in D1 involves two key steps:
- Remove a Node (e.g., Node A): Once Node A is removed, find the Minimum Spanning Tree (MST) of the remaining graph using Prim’s or Kruskal’s Algorithm (covered in Algorithms I).
- Re-attach the Shortest Links: Add back the two shortest arcs that originally connected Node A to the rest of the graph.
- Lower Bound Calculation: Lower Bound = MST weight + Sum of the two shortest links connecting back to A.
The actual TSP solution must be greater than or equal to this Lower Bound.
Upper Bound for TSP (Nearest Neighbour)
The simplest way to find an upper bound (a possible, but not guaranteed shortest, tour) is often using the Nearest Neighbour Algorithm.
- Start at the given node (S).
- Move to the nearest unvisited node.
- Repeat Step 2 until all nodes are visited.
- Return directly to the starting node (S).
The actual TSP solution must be less than or equal to this Upper Bound.
Crucial Distinction: Dijkstra’s finds the shortest route between two points. TSP finds the shortest complete circuit visiting all points. They are different problems solved using different techniques.
Congratulations! You have mastered the core algorithms for routing and path finding in Decision Mathematics. Keep practicing those label updates, and you'll find these questions very straightforward!