Mathematics | Algorithms on graphs II

Welcome to Algorithms on Graphs II!

Hello future Decision Mathematicians! This chapter dives into two of the most practical and widely used algorithms in network analysis. If you've ever used a navigation app or planned a delivery route, you've used the principles we're about to learn.

Don't worry if graph algorithms seemed tricky before—we’re breaking them down step-by-step. By the end of this unit, you will be a master at finding the shortest route between two points and the most efficient way to cover every street!

Why is this important? These algorithms are the heart of logistics, transportation planning, and communication network design. Mastering them ensures you can solve complex real-world optimisation problems efficiently.

---

Section 1: Finding the Shortest Path – Dijkstra’s Algorithm

1.1 What is Dijkstra's Algorithm?

Dijkstra’s Algorithm is a systematic method used to find the shortest distance (or minimum weight) from a specified starting node (vertex) to every other node in a network.

Analogy: Think of Dijkstra's as the method a SatNav uses. It calculates the fastest route from your current position to every possible junction, ensuring that when it tells you the final route, it has permanently verified that route is the absolute minimum possible distance.

Key Requirement: This algorithm only works correctly if all the weights (distances, times, costs) of the arcs are non-negative (i.e., they cannot be zero or negative).

1.2 Step-by-Step Guide to Applying Dijkstra’s Algorithm

Follow these steps carefully to ensure accuracy:

1. Start Node Initialisation: Label the start node \(S\) with the permanent label \( [0, -] \) (distance zero, no previous node).
2. Scanning and Temporary Labelling: Scan the node with the most recently established Permanent Label.
   • Look at all adjacent nodes that do not yet have a permanent label.
   • Calculate the distance: \( \text{New Distance} = \text{Permanent Label Distance} + \text{Arc Weight} \).
   • If the New Distance is less than the node’s current Temporary Label, replace the Temporary Label with the new, shorter one.
3. Making a Label Permanent: From all the current Temporary Labels, select the one with the smallest distance. Make this label permanent.
4. Repeat: Go back to Step 2 and scan the newly permanently labelled node.
5. Stop: Stop when the destination node has received a permanent label, or when all nodes have permanent labels (if you need the shortest path to all nodes).

How to Trace the Shortest Route

The previous node indicator \(P\) in the label \( [d, P] \) is crucial. To find the path, start at the destination node and work backwards, using the previous node indicator until you reach the start node.

Example: If the destination node \(E\) has the permanent label \( [25, C] \), it means the shortest distance is 25, and you arrived via node \(C\). You then check \(C\)'s label, and so on.

1.3 Common Mistakes and Tips

Mnemonic Aid: Remember the order of calculation: Permanent -> Arc Weight -> Temporary (P.A.T. it down!).

Mistake to Avoid (The Big Trap!): When scanning a node, you must use the distance from its Permanent Label, not an old Temporary Label, to calculate new distances. Always use the confirmed minimum distance for your starting point.

Tip for Exams: Always write down the full label \((d, P)\) or \([d, P]\). Don't just write the distance, as you need the previous node indicator for tracing the route back. Cross out old temporary labels clearly when replacing them.

---

Section 2: Traversing All Edges – The Chinese Postman Problem (CPP)

2.1 What is the Route Inspection Problem?

The Route Inspection Problem (often called the Chinese Postman Problem or CPP) aims to find the shortest route that travels along every arc (edge) in a network at least once, starting and finishing at the same node.

Analogy: This is the perfect model for a postman delivering mail, a snowplough clearing streets, or a refuse truck collecting waste—they must cover every street segment and return home efficiently.

Goal: Minimise the total length of the route by repeating the shortest possible arcs.

2.2 Understanding Odd and Even Vertices

The key to the CPP is identifying odd and even nodes.

• Even Vertex: A node where an even number of arcs meet. If all nodes in a network are even, a route traversing every arc exactly once (an Eulerian circuit) exists. The solution is simply the sum of all arc weights.
• Odd Vertex: A node where an odd number of arcs meet. For a closed route (starting and ending at the same point) to exist, we must always have an even number of odd vertices. We must repeat arcs to 'pair up' these odd vertices, effectively turning them into even vertices.

Did You Know? This problem was named the Chinese Postman Problem because it was first studied and solved by the Chinese mathematician Mei Ko Kwan in 1962.

2.3 The Chinese Postman Algorithm (Finding Minimum Repeats)

If there are odd vertices, the algorithm requires finding the shortest ways to pair them up and repeating those shortest paths.

Step 1: Identify all Odd Vertices

Count the degree (number of arcs) connected to each node. List all the odd vertices. (There will always be 2, 4, 6, etc., of them).

Step 2: Find all Possible Pairings

If you have \(2n\) odd vertices, you need to list all possible ways to pair them up.

• Example: If odd nodes are A, B, C, D (four nodes), you have three possible pairings:
  1. (A and B) combined with (C and D)
  2. (A and C) combined with (B and D)
  3. (A and D) combined with (B and C)

Step 3: Calculate the Shortest Distance for Each Pair

For each pair of odd vertices, find the shortest path between them. You must use the network weights (distances) to determine these shortest paths.

Crucial Point: If the shortest path between two odd nodes is not a direct arc, you may need to use inspection or even Dijkstra's Algorithm (Section 1) on that section of the network to confirm the minimum distance between the two points.

Step 4: Select the Minimum Total Pairing

Sum the distances in each pairing combination identified in Step 2. The combination with the smallest total distance is the set of arcs that must be repeated.

Step 5: Calculate the Total Route Length

The final length of the shortest route is calculated as:
\( \text{Total Route Length} = (\text{Sum of all arc weights in the network}) + (\text{Minimum total length of repeated arcs}) \)

2.4 Dealing with Different Types of Graphs

The CPP principles apply regardless of the graph structure:

• Directed Graphs: In D1, we usually deal with undirected graphs for the CPP. If dealing with directed graphs (where movement can only go one way), the concept is similar but much more complex (involving semi-Eulerian trails), and is typically outside the scope of the standard Edexcel D1 calculation unless specified otherwise. Assume undirected unless told otherwise.
• Non-Planar Graphs: The algorithm works on any connected graph, whether or not it is planar (can be drawn without edges crossing).

Example Walkthrough (Four Odd Vertices A, B, C, D)

Suppose the shortest paths between the odd nodes are:
AB = 10, AC = 15, AD = 8, BC = 7, BD = 12, CD = 6.

We compare the pairings:

1. (AB + CD): \( 10 + 6 = 16 \)
2. (AC + BD): \( 15 + 12 = 27 \)
3. (AD + BC): \( 8 + 7 = 15 \)

The minimum length to be repeated is 15 (paths AD and BC).

---

Final Encouragement

These algorithms require careful, systematic work, especially in the labelling process for Dijkstra’s and the pairing process for CPP. Use a pencil, be neat, and cross-check your totals.
You have the tools now to solve fundamental optimization problems that power the modern world. Keep practicing, and you will master these challenging concepts!