I have a fully connected graph $G=(V,E)$ with $n$ vertices. The edge weights $w(e)$ with $e\in E$ are non-negative and form a metric space (e.g. Hamming distance), thus for vertices $v,u,y \in V$, we have $w(v,y) \leq w(v,u)+w(u,y)$.  

However, it is *expensive* to calculate $w(\cdot)$. 


My question is, is there an algorithm that can calculate the minimum spanning tree, without calculating all $n(n-1)/2$ edge weights? 



Minimum Spanning Tree of Graph with Unknown Weights
In general the triangle inequality will not help. To see this, recall that the minimum spanning tree depends only on the relative order of the weights. Take an arbitrary MST problem and scale all the weights to lie in $[2,3]$. Now the triangle inequality is satisfied but the MST is the same.


To put it another way, if in your problem the edge weights all happen to lie in $[2,3]$, you must find the weight of every edge since the one you didn't find the weight of can still be the smallest no matter what the weights of all the other edges are.


On the other hand, I can imagine a heuristic that accumulates lower bounds and often argues itself out of computing weights of some edges in practical problems. It just can't guarantee to perform better than standard algorithms in the worst case.


