Finding best path for airline


#1


#2

you can find out the minimum spanning tree of this graph, using that all the nodes will be connected with minimum sum of distance. If weights are not given consider weight of each edge to be 1.