Introduction: Charting the Course of Decision Making

Welcome to the exciting world of Algorithms on Graphs! This chapter is the heart of Decision Mathematics. While graphs might look like simple diagrams, the algorithms we study here are the fundamental tools used in navigation systems (like GPS), logistics, network planning, and social media connections.

In simple terms, an algorithm is just a set of instructions designed to solve a specific problem. In this chapter, we will learn two main types of problems: finding the shortest route between points, and finding the cheapest way to connect all points.

Don't worry if this seems tricky at first; we will break down each process step-by-step. Mastering these techniques involves methodical thinking and careful recording of your work.

Quick Review: Graph Terminology (Prerequisites)

  • Node (or Vertex): A point on the graph (e.g., a city, a junction).
  • Edge (or Arc): The line connecting two nodes (e.g., a road, a pipe).
  • Weight: The value associated with an edge (e.g., distance, time, cost).
  • Network: A graph where the edges have weights.
  • Path: A route taken along the edges.
  • Tree: A connected graph that has no cycles (loops).

Section 1: Finding the Shortest Route - Dijkstra's Algorithm

The Goal of Dijkstra's Algorithm

Dijkstra's algorithm is used to find the shortest (or fastest, or cheapest) path from a single starting node to every other node in the network.

Analogy: Think of it as planning the fastest possible delivery route from a central warehouse (the start node) to every single customer in the city.

Step-by-Step Guide to Dijkstra's Algorithm

The algorithm uses two types of labels for each node:

  1. Permanent Labels: The definitive, shortest distance found so far to that node. Once permanent (or 'boxed'), it cannot change.
  2. Temporary Labels: The distance calculated via a potential route. These can be updated (scratched out and replaced) if a shorter route is found.

The Procedure:

  1. Start: Label the start node with a permanent label of \(0\). Box this number.
  2. Scan: Look at all unboxed nodes that are directly connected to the most recently boxed node.
  3. Calculate Temporary Labels: For each connected unboxed node, calculate its distance from the start via the currently boxed node.
    • New Label = (Permanent Label of current node) + (Weight of the connecting edge)
    If the new calculated distance is shorter than the node's existing temporary label (or if it has no label), replace the old label with the new one.
  4. Select and Box: Choose the smallest temporary label from all unboxed nodes in the entire network. Make this label permanent (box it).
  5. Repeat: Continue steps 2 to 4 until the destination node (or all nodes) has a permanent (boxed) label.

How to Trace the Shortest Path

Once you have finished the algorithm, to find the actual path from the start node to a specific destination node, you must work backwards from the destination.

  • Start at the destination node.
  • Look at its boxed label \(L\). Find a preceding node \(P\) such that \((\text{Label of } P) + (\text{Weight of Edge } P \to D) = L\).
  • The shortest path involves only those edges whose weights contribute to the permanent label sum.

⚠ Common Mistake to Avoid

A very common error is only calculating temporary labels based on the start node. Remember, you must always update the temporary labels based on the most recently boxed node. Furthermore, once a label is permanent (boxed), you can use it to scan, but you cannot change its value.

Key Takeaway for Dijkstra's: Dijkstra's method is about finding the shortest path outwards, step-by-step, by always making the shortest available route permanent before moving on.


Section 2: Connecting Everything - Minimum Spanning Trees (MST)

What is a Spanning Tree?

Imagine you have several locations (nodes) that you need to connect with cables or roads (edges). A Spanning Tree is a selection of edges that connects all the nodes in the network, using the minimum number of edges required, and crucially, without forming any cycles (loops).

What is a Minimum Spanning Tree (MST)?

A Minimum Spanning Tree (MST) is a spanning tree where the total weight of the chosen edges is as small as possible.

Analogy: If you are setting up a phone network across several towns, you want to ensure every town is connected, but you want to minimize the total length (and thus cost) of the cable you lay.

We use two powerful algorithms to find an MST: Prim's Algorithm and Kruskal's Algorithm. They always yield the same total minimum weight, but they approach the problem differently.


Section 3: Prim's Algorithm (Node-Focused Approach)

Prim's algorithm builds the MST by growing the tree outwards from a starting node. It is a node-based approach.

Memory Aid: P for Prim's, P for Proximity – we always pick the edge closest to the current growing tree.

Method 1: Prim’s on a Network Diagram

The Procedure:

  1. Start: Choose any node to begin the tree. Mark this node as 'in the tree' (often by highlighting it or the attached edges).
  2. Scan: Look at all the edges connected to the nodes currently in the tree.
  3. Select: Choose the edge with the smallest weight from this set of scanned edges, ensuring this edge connects to a node not yet in the tree.
  4. Add: Add this minimum weight edge and the new node it connects to the tree.
  5. Repeat: Continue steps 2 to 4 until all nodes are included in the tree.
  6. Total Weight: Sum the weights of the chosen edges to find the total minimum weight.

⚠ Prim's Crucial Rule

You only consider edges linked to nodes already selected. The moment an edge creates a cycle with existing edges in the tree, you MUST ignore it, even if it has the smallest weight.

Method 2: Prim’s Using a Matrix (Table)

Prim’s can be performed efficiently using a cost matrix, especially when the network is complicated.

  1. Start: Select a starting row/node (e.g., Node A). Mark this row as 'visited' (e.g., crossing out the row).
  2. Scan Row: Look across the selected row and find the smallest non-zero entry. Highlight this entry and record the edge.
  3. Select Column: The entry you highlighted corresponds to a new node (the column heading). Cross out this new node's row and column.
  4. Re-Scan: Now, look only at the columns of the nodes NOT yet crossed out. Find the minimum weight among all the active rows (rows of nodes already in the tree).
  5. Repeat: Continue selecting the minimum uncrossed value until \(n-1\) edges have been selected (where \(n\) is the number of nodes).

Key Takeaway for Prim's: Prim's is a greedy, localized approach. It always chooses the cheapest edge available from the nodes currently connected to the tree.


Section 4: Kruskal's Algorithm (Edge-Focused Approach)

Kruskal's algorithm builds the MST by looking at the entire network and selecting edges based purely on their weight, regardless of their position, provided they do not form a cycle.

Memory Aid: K for Kruskal's, K for Kicking out Cycles. This algorithm is all about selecting edges in order and rejecting any that complete a loop.

The Procedure for Kruskal's Algorithm

  1. List and Sort: List all the edges in the network and sort them into ascending order of weight (smallest to largest).
  2. Select Edges: Go down the sorted list, choosing edges one by one.
  3. Check for Cycles: Before selecting an edge, check if adding it creates a cycle (a closed loop) with any edges already selected.
    • If the edge does NOT create a cycle, select it (add it to the MST).
    • If the edge DOES create a cycle, reject it and move to the next edge on the list.
  4. Stop Condition: Stop when you have selected \(n-1\) edges, where \(n\) is the total number of nodes in the network. All nodes must be connected.
  5. Total Weight: Sum the weights of the selected edges.

Example of Kruskal's Selection

Imagine your list starts: Edge AB (weight 2), Edge CD (weight 3), Edge AC (weight 4), Edge BC (weight 5)...

1. Select AB (2). Tree starts.

2. Select CD (3). Fine, it's unconnected to AB.

3. Select AC (4). Fine, connects A and C.

4. Consider BC (5). If we select BC, we create a cycle: A-B-C-A. Therefore, REJECT edge BC.

Comparison: Prim's vs. Kruskal's

Both algorithms achieve the same result (the MST), but in practice:

  • Prim's is often easier to use if the network is represented as a matrix (table of distances).
  • Kruskal's is often easier to use if the network is represented as a long list of edges.

Key Takeaway for Kruskal's: Kruskal’s is about global optimization. Sort all edges first, then add them based on cost, relentlessly checking that you never form a closed loop.


Summary and Encouragement

Congratulations! You have covered the three foundational algorithms of Decision Mathematics 1:

  1. Dijkstra's Algorithm: Finds the shortest path from one node to all others (Node-Permanent Labeling).
  2. Prim's Algorithm: Builds a Minimum Spanning Tree by adding the closest unvisited node (Node-Focused).
  3. Kruskal's Algorithm: Builds a Minimum Spanning Tree by selecting edges in cost order, avoiding cycles (Edge-Focused).

The key to success in this chapter is practice. Each algorithm is a structured procedure. Stick to the steps, be meticulous with your labeling and checks, and you will master these vital techniques!


Did You Know?

Edsger Dijkstra invented his shortest path algorithm in 1956 while having coffee with his wife, and solved the problem in about 20 minutes! This shows that even the most famous algorithms can be derived from simple, logical steps.