The Shortest Pipe Problem — How to Connect Points Using the Least Material

Imagine you’re building a water system for a small neighborhood. There are 5 houses, and you need to connect them all with pipes. You want to use as little pipe as possible to save money.

How do you figure out the best route?

This is called the minimum network problem, and it’s the same math that engineers use to design oil and gas pipelines worth millions of dollars.

Setting Up the Problem

Let’s say we have 4 houses on a grid:

        B
        |
        |
A ------+------ C
        |
        |
        D

Each house has a position. In math, we use coordinates — just like a map:

House A is at position $(1, 3)$
House B is at position $(3, 5)$
House C is at position $(5, 3)$
House D is at position $(3, 1)$

Measuring Distance

To find the distance between two points, we use the distance formula — which is just the Pythagorean theorem ( $a^2 + b^2 = c^2$ ) in disguise:

\text{distance} = \sqrt{(\Delta x)^2 + (\Delta y)^2}

For example, the distance from A $(1,3)$ to B $(3,5)$ :

d = \sqrt{(3-1)^2 + (5-3)^2} = \sqrt{4 + 4} = \sqrt{8} \approx 2.83

The Wrong Way: Connect Everything

You might think: “Just draw a line from every house to every other house.” That works, but it uses way too much pipe. With 4 houses, you’d need 6 separate pipes!

The number of pipes if you connect everything:

\text{pipes} = \frac{n \times (n-1)}{2}

For 4 houses: $\frac{4 \times 3}{2} = 6$ pipes. Wasteful.

The Smart Way: Minimum Spanning Tree

Here’s the trick: you only need 3 pipes to connect 4 houses. The rule is:

To connect $n$ points, you need exactly $n - 1$ pipes.

4 houses → 3 pipes. 10 houses → 9 pipes. 100 houses → 99 pipes.

But which 3 pipes? You want the 3 shortest ones that still connect everyone.

The Algorithm (Step by Step)

List all possible connections and their distances
Sort them from shortest to longest
Pick the shortest one — draw that pipe
Pick the next shortest — but only if it connects a new house (no loops!)
Repeat until all houses are connected

Let’s try it with our 4 houses:

Connection	Distance
A → B	$\sqrt{8} \approx 2.83$
B → C	$\sqrt{8} \approx 2.83$
C → D	$\sqrt{8} \approx 2.83$
A → D	$\sqrt{8} \approx 2.83$
A → C	$\sqrt{16} = 4.00$
B → D	$\sqrt{16} = 4.00$

Sorted (shortest first): A→B, B→C, C→D, A→D are all tied at 2.83.

Pick A→B ✓ (connects A and B) Pick B→C ✓ (connects C to the group) Pick C→D ✓ (connects D to the group)

Done! Total pipe: $2.83 + 2.83 + 2.83 = 8.49$ units.

We skipped A→D because by then D was already connected through B→C→D. Adding it would create a loop — a waste of pipe.

The Secret Trick: Adding a Junction

What if you’re allowed to add a new point — not a house, just a junction where pipes meet?

Look at this:

        B
       /
      J        ← junction point (not a house)
     / \
    A    C
     \ /
      J2       ← another junction
       \
        D

By placing junction points in clever locations, you can make the total pipe length even shorter. The pipes meet at $120°$ angles — that’s the most efficient configuration.

This is called a Steiner tree, named after mathematician Jakob Steiner.

How Much Does It Save?

The maximum savings from adding junctions is about 13%:

\text{savings} \leq 1 - \frac{\sqrt{3}}{2} \approx 13.4\%

That might not sound like much, but when you’re building a $50 million pipeline network, 13% = **$ 6.5 million saved**.

Try It Yourself

Here’s a simple Python script you can run to find the shortest network:

# You need: pip install numpy scipy matplotlib

import numpy as np
from scipy.spatial.distance import pdist, squareform
from scipy.sparse.csgraph import minimum_spanning_tree
import matplotlib.pyplot as plt

# Our 4 houses
houses = np.array([
    [1, 3],  # A
    [3, 5],  # B
    [5, 3],  # C
    [3, 1],  # D
])
labels = ['A', 'B', 'C', 'D']

# Step 1: Calculate all distances
distances = squareform(pdist(houses))

# Step 2: Find the shortest network (MST)
mst = minimum_spanning_tree(distances)

# Step 3: Draw it
fig, ax = plt.subplots(1, 1, figsize=(6, 6))

# Draw the pipes
for i, j in zip(*mst.nonzero()):
    ax.plot([houses[i,0], houses[j,0]],
            [houses[i,1], houses[j,1]],
            'b-', linewidth=2)

# Draw the houses
for idx, (x, y) in enumerate(houses):
    ax.plot(x, y, 'ro', markersize=12)
    ax.annotate(labels[idx], (x+0.15, y+0.15), fontsize=14)

ax.set_title(f'Shortest Network: {mst.sum():.2f} units of pipe')
ax.set_aspect('equal')
ax.grid(True, alpha=0.3)
plt.savefig('shortest_network.png')
plt.show()

print(f"Total pipe needed: {mst.sum():.2f} units")

Real-World Applications

This exact math is used for:

Oil & gas pipelines — connecting well pads to processing facilities
Internet cables — connecting cities with fiber optic lines
Road networks — designing highway systems
Circuit boards — connecting chips with the shortest wires
Power grids — connecting substations

Key Takeaways

Concept	What It Means
Coordinates	Every point has an $(x, y)$ position
Distance formula	$\sqrt{(\Delta x)^2 + (\Delta y)^2}$
Minimum spanning tree	The shortest network using $n-1$ pipes for $n$ points
Steiner point	A junction that reduces total pipe length by up to 13%
No loops	Every pipe must connect something new

The next time you see a network of roads, wires, or pipes, you’ll know — someone solved this math problem to build it.

This article uses concepts from graph theory and computational geometry — topics usually taught in college, but the core ideas are simple enough for anyone to understand.