Irrigation Network Design

MINIMUM SPANNING TREE

Agriculture accounts for 70% of global freshwater withdrawals, and unplanned pipe layouts waste 15–30% of installation budgets. Before trenching begins, a farm must decide which pipe segments to install connecting source to fields. This is the Minimum Spanning Tree problem — solved optimally in polynomial time.

Where This Decision Fits

Agricultural water management — the highlighted step is what this page optimizes

Crop PlanningLand use & crop selection

→

Seed ProcurementOrdering seed & inputs

→

PlantingField assignment & sowing

→

Irrigation SchedulingPipe network & water flow

→

HarvestEquipment scheduling

→

Post-HarvestStorage, transport & sales

The Problem

From irrigation pipes to optimization theory

A farm must connect a water source to 7 fields via an irrigation pipe network. Potential pipe segments have different installation costs based on terrain and distance. The goal is to connect all fields at minimum total cost without cycles.

This is the Minimum Spanning Tree (MST) problem: find a tree connecting all vertices with minimum total edge weight. Solved optimally in polynomial time.

	Agriculture Domain	MST Model
	Water source	Node (vertex)
	Field	Node (vertex)
	Pipe segment	Edge
	Installation cost	Edge weight w(e)
	Connected network	Spanning tree

MST — Kruskal O(E log E), Prim O(E log V) — polynomial-time exact

Explore the Location & Network Family

Try It Yourself

Edit node positions, edge costs, and find the cheapest irrigation pipe network

Network Nodes & Edges

8 Nodes · 15 Edges · Click any cell to edit

Choose a Scenario

A small irrigated farm with 1 well pump station and 7 field zones. Terrain is relatively flat, and pipe costs range from $7K to $25K per segment depending on distance and soil type.

Nodes (Fields & Source)

ID	Label	X	Y

Edges (Pipe Segments) — cost in $K

From	To	Cost ($K)

Select Algorithm

Irrigation Network Graph

The Algorithms

Two exact approaches — same optimal cost, different edge-selection strategies

Kruskal’s Algorithm (Edge-Sorting)

Sort All Edges

Sort edges by weight in ascending order. Cheapest pipe segments are considered first.

Initialize Union-Find

Each node starts in its own component. Union-Find tracks connected components efficiently.

Add Edges Greedily

For each edge (cheapest first), add it if it connects two different components. Skip if it would create a cycle.

Stop at n−1 Edges

After adding n−1 edges, all nodes are connected. The result is the minimum spanning tree.

Prim’s Algorithm (Vertex-Growing)

Start from Any Node

Initialize the tree with a single node (e.g., the water source). Mark it as “in the tree.”

Find Cheapest Crossing Edge

Among all edges from tree nodes to non-tree nodes, pick the lightest.

Grow the Tree

Add the chosen edge and its new endpoint to the tree. Update the frontier of candidate edges.

Repeat Until Complete

Continue until all nodes are in the tree. Both algorithms yield the same optimal MST cost.

Real-World Complexity

Factors beyond the basic MST model

Terrain Variation

Hilly terrain affects pipe pressure requirements and installation costs.

Flow Capacity

Pipes have maximum flow rates; downstream fields may need larger pipes.

Frost Protection

Pipes must be buried below frost line, varying cost by region.

Crop Water Needs

Different crops need different flow rates, affecting pipe sizing.

Maintenance Access

Pipe network must be accessible for repairs, adding routing constraints.

Pump Stations

Long pipe runs need booster pumps, adding fixed-cost nodes.

References

Key literature on minimum spanning trees

Kruskal, J.B. (1956).

"On the shortest spanning subtree of a graph."

Proceedings of the AMS, 7(1), 48–50.

Prim, R.C. (1957).

"Shortest connection networks and some generalizations."

Bell System Technical Journal, 36(6), 1389–1401.

Need to optimize irrigation
infrastructure costs?

Get in Touch

Data shown is illustrative. This is a simplified model for educational purposes.