[Home Page - Algorithms](/@roger61205/Algorithms)
[toc]

Let $G=(V,E)$ be a connected, undirected and weighted path.
# Kou
## Algorithm
### Metric Closure
The metric closure of a graph $G$ is the complete graph in which each edge is weighted by the shortest path distance between the nodes in $G$.
1. Step 1
Create an empty list $M$ for the metric closure.
2. Step 2
Find the all-pairs shortest path on $G$.
3. Step 3
For each $u\in V$, add the shortest path from $u$ to another $v\in V$ to $M$.
### Method
1. Step 1
Create a metric closure $M$
2. Step 2
Create a subgraph $H$ including only terminal nodes.
3. Step 3
Find the edges of the minimum spanning tree of $H$.
4. Step 4
Find the MST again, over the new set of edges.
5. Step 5
Removes nodes that are not in the Stenier tree.

**References**
[NetworkX - GitHub](https://github.com/networkx)