给定n个城市，并创建一个n*n的距离矩阵来存放两两城市之间的距离，当两个城市之间不能直达时，将距离记为无穷大。对矩阵进行初始化：
for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { arcs[i][j] = Double.POSITIVE_INFINITY; if (i == j) { arcs[i][j] = 0; } } }
check数组记录此城市是否已经被添加到树中，dist数组用于表示起始点到i点的距离。给出起始点C1：
for (int i = 0; i < N; i++) { check[i] = false; dist[i] = arcs[C1][i]; }
每次找出距离当前点最近的下一个点，进行放松
int c = -1; while (c != C2) { double d = Double.POSITIVE_INFINITY; for (int i = 0; i < N; i++) { if (check[i] == true) { continue; } else { if (dist[i] < d) { c = i; d = dist[i]; } } } check[c] = true; for (int i = 0; i < N; i++) { if (check[i] == true) { continue; } else { if ((dist[i] - dist[c] - arcs[c][i]) > 0) { dist[i] = dist[c] + arcs[c][i]; } } } }
原文：https://www.cnblogs.com/tenghaoxiang/p/10084477.html