Euclidean Network¶

Definition¶

In the course's Euclidean network, cities have plane coordinates $(x_i,y_i)$ , an edge may join every pair of cities, and its length is

d_{ij}=\sqrt{(x_i-x_j)^2+(y_i-y_j)^2}.

The resulting distances provide the weights for the minimum spanning tree problem.

Interpretation¶

Coordinates turn a location problem into a complete weighted network: every pair of cities is joined by an edge, and the length of that edge is the straight-line distance between the two points, computed with Pythagoras' theorem. These are straight-line lengths, not road distances or travel times.

Four cities at grid points joined by straight edges of all pairs, with the edge between cities 1 and 2 highlighted, of length the square root of 13.

The four cities lie at the grid points $(1,1)$ , $(4,3)$ , $(5,1)$ and $(2,3)$ , and all $6$ pairs are joined. The red edge between cities 1 and 2 spans $3$ units horizontally and $2$ vertically, so $d_{12}=\sqrt{3^2+2^2}=\sqrt{13}\approx3.61$ $3.61$ . The coordinates only fix the edge lengths; they add no further connections.

With $n$ cities there are $n(n-1)/2$ edges, so the seven-city example already needs 21 distances. Since $d_{ij}=d_{ji}$ $d_{j i}$ , the network is undirected. Straight-line distances also have a useful property: going from $i$ to $j$ via a third city is never shorter than the direct edge, so in a Euclidean network the direct edge is always a shortest path between its endpoints.

Many distances are irrational numbers, and different edges can have equal or nearly equal lengths: in the figure, the edges $1-2$ and $3-4$ both have length $\sqrt{13}$ . Rounding too early can therefore change the comparison between two close edges. Once the distances are computed accurately, the Dijkstra-Prim and Kruskal methods for a minimum spanning tree apply without change.

Key Results¶

Distances are symmetric: $d_{ij}=d_{ji}$ $d_{j i}$ .
Use sufficient precision when comparing close distances.
The usual spanning-tree algorithms apply once the distance matrix is computed.

Examples¶

The red edge has length $d_{12}=\sqrt{3^2+2^2}=\sqrt{13}$ $13$ . Euclidean distances satisfy the triangle inequality and can also be used as routing costs.

Between $(13,6)$ and $(15,9)$ the distance is $\sqrt{13}\approx3.61$ $3.61$ .
The seven-city example has tree length about 27.29 using the displayed rounded distances.

Prerequisites¶

Sources¶

OR Modelling · Week 4

Symbols: square root

Last updated: 20 October 2026 03:02