Graph should be working properly. I think greedy works now. Tried it on a 131-city data set and got 631.01 vs optimal of 564.