DSA Minimum Cost to Connect All Points

The problem

A set of points sits in a plane. Any two points can be linked, and a link costs the Manhattan distance between them. The task finds the cheapest network that joins every point.

The Manhattan distance between two points adds the horizontal gap and the vertical gap. A network joining every point with no wasted links is a tree, so the answer uses exactly one link fewer than the point count.

cases = [
    ([(0, 0), (2, 2), (3, 10), (5, 2), (7, 0)], 20),
    ([(0, 0), (1, 1), (1, 0)], 2),
    ([(0, 0), (3, 4)], 7),
    ([(4, 4)], 0),
]
for points, expected in cases:
    print("points:", points, "minimum cost:", expected)

The five-point case is the main example. Its cheapest network costs 20. The single point costs nothing, because it is already connected to itself.

Intuition: always link the nearest point next

The first idea starts at one point and repeatedly links the nearest point not yet reached. Each step is locally cheapest. The chain it builds is not.

Local greed spends cheap links early and strands a far point. The stranded point then pays a long link that a different order would have shared. The trap below runs on the main case.

def manhattan(p, q):
    return abs(p[0] - q[0]) + abs(p[1] - q[1])

points = [(0, 0), (2, 2), (3, 10), (5, 2), (7, 0)]
seen = [0]
total = 0
while len(seen) < len(points):
    u = seen[-1]
    nxt = min((i for i in range(len(points)) if i not in seen),
              key=lambda i: manhattan(points[u], points[i]))
    total += manhattan(points[u], points[nxt])
    print("link", points[u], "->", points[nxt], "cost", manhattan(points[u], points[nxt]))
    seen.append(nxt)
print("chain total:", total)
print("minimum cost:", 20)

The chain pays 25 against an optimum of 20. Its last link, from (7, 0) up to (3, 10), costs 14 alone. The optimal network reaches the high point from (2, 2) for 9 instead.

Brute force: try every possible network

Every pair of points is a possible link, so five points offer ten candidate links. The brute force tries every set of four links. It keeps the cheapest set that connects all five points.

A set connects the points when a walk from the first point reaches all of them through chosen links. Sets with a cycle or a stranded point fail the test.

from itertools import combinations

def manhattan(p, q):
    return abs(p[0] - q[0]) + abs(p[1] - q[1])

def connects_all(points, chosen):
    graph = {i: [] for i in range(len(points))}
    for i, j in chosen:
        graph[i].append(j)
        graph[j].append(i)
    seen = {0}
    stack = [0]
    while stack:
        u = stack.pop()
        for v in graph[u]:
            if v not in seen:
                seen.add(v)
                stack.append(v)
    return len(seen) == len(points)

points = [(0, 0), (2, 2), (3, 10), (5, 2), (7, 0)]
pairs = [(i, j) for i in range(5) for j in range(i + 1, 5)]
tried = 0
best = None
for chosen in combinations(pairs, 4):
    tried += 1
    if connects_all(points, chosen):
        cost = sum(manhattan(points[i], points[j]) for i, j in chosen)
        if best is None or cost < best:
            best = cost
print("link sets tried:", tried)
print("minimum cost:", best)

The brute force tries 210 sets for five points. Six points would offer 15 links and 3003 sets of five. The set count explodes long before the point count looks large.

The optimal solution: Prim's method, cheapest known link per point

Prim's method grows one tree from a starting point, and it keeps for each outside point only the cheapest known link into the tree. That one array is the whole state.

Each step joins the outside point with the smallest kept cost. The new point then offers its own links, and any cheaper offer replaces the stored one. No edge list is ever built, so memory stays proportional to the point count.

Ties break toward the smaller point index in this article's code. The rule keeps the printed join order identical on every run, and it never changes the total.

def manhattan(p, q):
    return abs(p[0] - q[0]) + abs(p[1] - q[1])

def connect(points):
    n = len(points)
    if n <= 1:
        return 0, 0, []
    in_tree = [False] * n
    best = [10 ** 9] * n
    best[0] = 0
    total = 0
    measured = 0
    joins = []
    for step in range(n):
        u = -1
        for i in range(n):
            if not in_tree[i] and (u == -1 or best[i] < best[u]):
                u = i
        in_tree[u] = True
        total += best[u]
        if step > 0:
            joins.append((u, best[u], total))
        for v in range(n):
            if not in_tree[v]:
                d = manhattan(points[u], points[v])
                measured += 1
                if d < best[v]:
                    best[v] = d
    return total, measured, joins

cases = [
    [(0, 0), (2, 2), (3, 10), (5, 2), (7, 0)],
    [(0, 0), (1, 1), (1, 0)],
    [(0, 0), (3, 4)],
    [(4, 4)],
]
for points in cases:
    total, measured, joins = connect(points)
    print("points:", points)
    print("minimum cost:", total, "distances measured:", measured)

Both multi-point cases match the expected totals. Only ten distances were measured for the five-point case, although ten links exist and the brute force weighed 210 sets. Measuring on demand replaces storing and sifting every link.

Walkthrough: growing the tree over five points

The walk starts with point (0, 0) alone in the tree. Each printed step joins one point and then shows the cheapest known link for every point still outside. The array is the state to watch.

def manhattan(p, q):
    return abs(p[0] - q[0]) + abs(p[1] - q[1])

points = [(0, 0), (2, 2), (3, 10), (5, 2), (7, 0)]
n = len(points)
in_tree = [False] * n
best = [10 ** 9] * n
best[0] = 0
total = 0
for step in range(n):
    u = -1
    for i in range(n):
        if not in_tree[i] and (u == -1 or best[i] < best[u]):
            u = i
    in_tree[u] = True
    total += best[u]
    for v in range(n):
        if not in_tree[v]:
            best[v] = min(best[v], manhattan(points[u], points[v]))
    outside = [(points[i], best[i]) for i in range(n) if not in_tree[i]]
    print("joined", points[u], "at cost", best[u],
          "| total so far:", total, "| best links outside:", outside)
print("final total:", total)

The high point (3, 10) keeps a costly link for most of the walk. Its price falls to 9 only when (2, 2) joins. Joining in cheapest order lets that fall happen before the high point is taken.

Complexity

Prim's method here measures each pair of points at most once across the whole run, so its time is O(n^2) for n points. It stores one cost and one flag per point, so its extra space is O(n).

The brute force counts sets, not pairs. Its set count is the number of ways to choose n minus 1 links from all pairs, and that count grows faster than any polynomial.

import math
for n in [4, 5, 6, 7]:
    pairs = n * (n - 1) // 2
    sets = math.comb(pairs, n - 1)
    print("points", n, "- link sets to try:", sets,
          " distances Prim measures:", pairs)

Seven points already mean 54264 sets against 21 measured distances. The counting needs no clock. The brute force is a correctness check for tiny inputs, never a method.

Edge cases and pitfalls

Duplicate points link for zero. A zero link is real progress, because it joins a point for free. Code that treats zero as no link can loop or overpay.

The common mistake prices links with the straight-line distance from geometry. The problem charges the Manhattan distance. The pair (0, 0) and (3, 4) separates the two, charging 7 here against a straight-line 5.

def manhattan(p, q):
    return abs(p[0] - q[0]) + abs(p[1] - q[1])

def connect(points):
    n = len(points)
    if n <= 1:
        return 0, 0, []
    in_tree = [False] * n
    best = [10 ** 9] * n
    best[0] = 0
    total = 0
    measured = 0
    joins = []
    for step in range(n):
        u = -1
        for i in range(n):
            if not in_tree[i] and (u == -1 or best[i] < best[u]):
                u = i
        in_tree[u] = True
        total += best[u]
        if step > 0:
            joins.append((u, best[u], total))
        for v in range(n):
            if not in_tree[v]:
                d = manhattan(points[u], points[v])
                measured += 1
                if d < best[v]:
                    best[v] = d
    return total, measured, joins

print("one point:", connect([(4, 4)]))
print("two points:", connect([(0, 0), (3, 4)]))
print("duplicate points:", connect([(1, 1), (1, 1), (2, 1)]))
print("collinear points:", connect([(0, 0), (0, 3), (0, 6)]))
print("manhattan (0,0)-(3,4):", manhattan((0, 0), (3, 4)))

The collinear case pays 6, the cost of two short hops. A single long link from end to end would pay the same distance again for no gain. The tree shape follows the cheap links on its own.