Introduction to Network Algorithms

Welcome to the world of Network Algorithms! This chapter is part of your Discrete Mathematics studies. Imagine you are trying to find the quickest way to school using Google Maps, or an engineer trying to connect several towns with fiber-optic cables using the least amount of material. These are real-world "network" problems.

In this chapter, we will learn how to use specific step-by-step rules—called algorithms—to solve these problems efficiently. Don't worry if it seems like a lot of steps at first; once you see the patterns, it becomes much like following a recipe!

1. Shortest Path: Dijkstra's Algorithm

The goal here is simple: find the least weight path (usually the shortest distance or cheapest cost) between two specific points (vertices) in a network.

How Dijkstra’s Algorithm Works

Think of this like a "controlled explosion." We start at our beginning point and slowly "label" nearby points with their distance from the start until we reach our destination.

Step-by-Step Process:

  1. Label the start vertex with a permanent label of 0.
  2. From the vertex you just made permanent, look at all adjacent (connected) vertices that don't have permanent labels yet.
  3. Calculate working values (temporary distances) for these neighbors: \( \text{New Value} = \text{Value at Current Permanent Vertex} + \text{Weight of Edge} \).
  4. If the new value is smaller than a previous working value, replace it.
  5. Pick the vertex in the whole network with the smallest working value. Make this your new permanent label.
  6. Repeat until your destination vertex has a permanent label.

Quick Review: Labels usually have three parts: the Vertex name, the Order in which it became permanent, and the Final Distance.

Efficiency (Order): Dijkstra’s algorithm has quadratic order, written as \( O(V^2) \), where \( V \) is the number of vertices. This means if you double the number of towns, the computer might take four times as long to solve it!

Common Mistake to Avoid: Always choose the smallest working value from the entire network to make permanent next, not just the ones connected to your current point!

Key Takeaway

Dijkstra’s Algorithm is the go-to tool for finding the absolute shortest route between two specific points in a weighted network.


2. Minimum Spanning Trees (MST)

Sometimes we don't just want to get from A to B; we want to connect every point in the network together using the minimum total edge weight. This is called a Minimum Connector or Minimum Spanning Tree.

Prim’s Algorithm

Prim’s is "vertex-based." You start at one point and grow your tree like a plant, always adding the cheapest branch available that connects to a new point.

  • Graphical Method: Choose a starting vertex. Add the shortest edge connected to it. Now look at all edges connecting the vertices you already have to vertices you don't have yet. Pick the shortest one. Repeat!
  • Tabular/Matrix Method: If given a distance table, you cross out rows and look for the smallest value in the columns of the "connected" vertices.

Kruskal’s Algorithm

Kruskal’s is "edge-based." It’s even simpler but requires a bit of care to avoid "cycles" (closed loops).

  1. Sort all edges in the network from shortest to longest.
  2. Pick the shortest edge.
  3. Pick the next shortest edge. If it forms a cycle (a loop), reject it and move to the next.
  4. Keep going until every vertex is connected.

Memory Aid: Prim starts at a Point. Kruskal starts with a Katalog of edges.

Efficiency: Both Prim’s and Kruskal’s algorithms have cubic order, or \( O(V^3) \). They are slightly "heavier" for computers than Dijkstra's.

Key Takeaway

Use Prim’s or Kruskal’s to connect every node with the least total weight. Prim's grows from a point; Kruskal's picks the best edges from a list.


3. The Travelling Salesperson Problem (TSP)

In this problem, a salesperson must visit every vertex and return to the start, minimizing the total distance. This is much harder than an MST because we must follow a specific "cycle."

Because the "perfect" answer is very hard to find for large networks, we find a range (bounds) where the answer must lie.

Upper Bound: Nearest Neighbour Method

This is a "greedy" approach. Starting at a vertex, always go to the nearest vertex you haven't visited yet. Once you've visited them all, go straight back to the start.

Did you know? This method might "stall" if a network isn't "complete" (meaning not every town has a direct road to every other town). You might have to take a longer path to get to a far-off town or to get back home.

Lower Bound: MST Method

To find a lower bound (a value we know the real answer must be greater than or equal to):

  1. "Delete" one vertex and all edges connected to it.
  2. Find the Minimum Spanning Tree (MST) for the remaining vertices.
  3. Add the weights of the two shortest edges that were connected to the deleted vertex.
  4. The result is a lower bound. Repeating this for different deleted vertices gives different bounds; the highest value is the most useful "best" lower bound.
Key Takeaway

The Nearest Neighbour gives an Upper Bound (a "good enough" route). The Deleted Vertex + MST method gives a Lower Bound (the mathematical "floor" for the cost).


4. Route Inspection: The Chinese Postman Problem

Imagine a postman who needs to walk down every single street (edge) in a neighborhood at least once and return to the depot. To be efficient, he wants to minimize the distance he has to walk twice.

The Rule of Degrees

If every vertex in a network has an even degree (an even number of edges meeting there), the postman can travel every edge exactly once. This is an Eulerian circuit.

If there are odd nodes (vertices with an odd degree), the postman must repeat some edges.

Solving for Odd Nodes

We must pair up the odd nodes and find the shortest paths between them to "double up."

  • 2 odd nodes: Find the shortest path between them (using Dijkstra if needed) and add that weight to the total of all edges.
  • 4 odd nodes: There are 3 ways to pair them. For example, if nodes are A, B, C, D, you could pair (AB, CD), (AC, BD), or (AD, BC). Calculate the total "extra" weight for each pairing and choose the minimum.
  • 6 odd nodes: This gets trickier! There are 15 possible pairings.

Important Formula: For \( 2n \) odd nodes, the number of pairings is given by: \( 1 \times 3 \times 5 \times ... \times (2n - 1) \).

Example: For 4 odd nodes (\( n=2 \)), the formula is \( 1 \times 3 = 3 \) pairings. For 6 odd nodes (\( n=3 \)), it is \( 1 \times 3 \times 5 = 15 \) pairings.

Key Takeaway

The Route Inspection Problem is about making all nodes "even" by repeating the shortest possible paths between pairs of odd nodes.


Final Quick Review Box

Dijkstra: Shortest path between two points. \( O(V^2) \).
Prim/Kruskal: Shortest way to connect all points. \( O(V^3) \).
Nearest Neighbour: Finding an Upper Bound for a tour (TSP).
MST on Reduced Network: Finding a Lower Bound for a tour (TSP).
Route Inspection: Traversing every edge; pairs up odd nodes.

Don't worry if this seems tricky at first! The best way to learn these is to grab a piece of paper, draw a small network, and physically trace the steps of the algorithms yourself. You've got this!