t.s.


{ a->b : a -> X = min a -> Z }

set of segments a -> b, such that the distance a -> b is the minimum where b can be any of the other cities


proof

consider the segment a -> b -> c -> d

replace it with a -> c -> b -> d

the distance 	a->c > a -> b
		c->b > c -> d
		b->d > b -> c

so all three cities are connected to longer paths than previously

this can be done for any other combination, other than the original set

in all cases the paths are longer

therefore, the original set has the shortest path.


assume that the 4 cities form the entire input set

follow the same argument for larger input sets


X the destination city

Z the set of all cities excluding a



the > signs are techically >=

