55
}
56
}
57
}
58
}
59
}
60
if(minI>-1){
61
edge=new Edge(minI,minJ,minds);
62
}
63
return edge;
64
}
65
66
// 计算空间距离
67
private double getDistance(City city1, City city2) {
68
double distance=Math.pow(city1.getX()-city2.getX(),2)+Math.pow(city1.getY()-city2.getY(),2);
69
return Math.sqrt(distance);
70
71
}
72
73
74
}
第一步肯定是算出临近距离矩阵
3，测试一下
01
public static void main(String[] args) {
02
List
03
04
City city0 = new City();
05
city0.setName("北 京");
06
city0.setX(116.28);
07
city0.setY(39.54);
08
citys.add(city0);
09
10
City city1 = new City();
11
city1.setName("上 海");
12
city1.setX(121.29);
13
city1.setY(31.14);
14
citys.add(city1);
15
16
City city2 = new City();
17
city2.setName("天 津");
18
city2.setX(117.11);
19
city2.setY(39.09);
20
citys.add(city2);
21
22
City city3 = new City();
23
city3.setName("重 庆");
24
city3.setX(106.32);
25
city3.setY(29.32);
26
citys.add(city3);
27
28
29
city4.setName("哈尔滨");
30
city4.setX(126.41);
31
city4.setY(45.45);
32
citys.add(city4);
33
34
City city5 = new City();
35
city5.setName("长 春");
36
city5.setX(125.19);
37
city5.setY(43.52);
38
citys.add(city5);
39
40
City city6 = new City();
41
city6.setName("南 京");
42
city6.setX(118.50);
43
city6.setY(32.02);
44
citys.add(city6);
45
46
City city7 = new City();
47
city7.setName("武 汉");
48
city7.setX(114.21);
49
city7.setY(30.37);
50
citys.add(city7);
51
52
City city8 = new City();
53
city8.setName("台 北");
54
city8.setX(121.31);
55
city8.setY(25.03);
56
citys.add(city8);
57
58
City city9 = new City();
59
city9.setName("香 港");
60
city9.setX(114.10);
61
city9.setY(22.18);
62
citys.add(city9);
63
64
MST mst=new MST(citys);
65
List
66
67
System.out.println("------------------线路最佳方案如下------------------");
68
for(Edge edge:edges){
69
City from=citys.get(edge.getI());
70
City to=citys.get(edge.getJ());
71
double length=edge.getW();
72
System.out.println(edge.getI()+"========>"+edge.getJ());
73
System.out.println(from.getName()+"到"+to.getName()+",全长"+length);
74
}
75
76
}
作者：AngelAndAngel