--sunfruit
求上圖1點到其他各點的最短路徑，依據(jù)圖論知識建立矩陣模型，進(jìn)一步得到代碼如下
public class ShortPathA {
private static int[][]
a = {
{0, 50, 10, 100000, 45, 100000}, {100000, 0, 15, 100000, 10, 100000}, {20, 100000, 0, 15, 100000, 100000}, {
100000, 20, 100000, 0, 35, 100000}, {100000, 100000, 1000000, 30, 0, 100000}, {100000, 100000, 100000, 3, 100000, 0}
};
private static boolean[] mark = new boolean[a.length];
public ShortPathA() {
int Vo = 0; //源點
//源點到其他各點的距離
int[] b = new int[a.length];
DynArrayInt S = new DynArrayInt();
for (int i = 0; i < a.length; i++) {
mark[i] = false;
//b[i] = a[Vo][i];
}
int best = -1;
mark[0] = true;
b[0] = 0; //{0為源點}
while (best != 0) {
best = 0;
int best_j = 0;
for (int i = 0; i < b.length; i++)
{
if (mark[i]) //{對每一個已計算出最短路徑的點}
{
for (int j = 0; j < b.length; j++) {
if ( (!mark[j]) && (a[i][j] > 0)) {
if ( (best == 0) || (b[i] + a[i][j] < best)) {
best = b[i] + a[i][j];
best_j = j;
}
}
}
}
}
if (best > 0) {
b[best_j] = best;
mark[best_j] = true;
}
}
System.out.println(java.util.Arrays.toString(b));
}
public static void main(String[] args) {
ShortPathA shortpath = new ShortPathA();
}
}