我爲對稱的無向圖實現了Floyd-Warshall算法。目前,我已經計算出每個連接點的最佳路徑。我的問題是,我想保存收集到累計重量的索引點,以便能夠稍後寫入路線中的點的名稱。我想將它們保存到列表中,但我不知道應將哪些索引寫入函數addDrawPointsToList(int a,int b,int [] [] M)。 a和b是點之間我想保存航點Floyd-Warshall算法 - 最短路徑 - 將路徑索引保存到數組
- 0 - 在同一節點
- 1 - 有節點之間的連接
- X - 沒有連接= 999重量
CODE:
public class FloydWarshallAlg {
static int[][] P;
static List<Integer> lista;
static final int N = 43;
static final int X = 999;
public static void main(String[] args) {
int M[][] = new int[][]{
{0, 1, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X},
{1, 0, 1, X, X, 1, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X},
{X, 1, 0, 1, 1, 1, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X},
{X, X, 1, 0, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X},
{X, X, 1, X, 0, X, 1, 1, 1, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X},
{X, 1, 1, X, X, 0, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X},
{X, X, X, X, 1, X, 0, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X},
{X, X, X, X, 1, X, X, 0, 1, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X},
{X, X, X, X, 1, X, X, 1, 0, 1, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X},
{X, X, X, X, X, X, X, X, 1, 0, 1, 1, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X},
{X, X, X, X, X, X, X, X, X, 1, 0, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X},
{X, X, X, X, X, X, X, X, X, 1, X, 0, 1, 1, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X},
{X, X, X, X, X, X, X, X, X, X, X, 1, 0, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X},
{X, X, X, X, X, X, X, X, X, X, X, 1, X, 0, 1, 1, 1, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X},
{X, X, X, X, X, X, X, X, X, X, X, X, X, 1, 0, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X},
{X, X, X, X, X, X, X, X, X, X, X, X, X, 1, X, 0, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X},
{X, X, X, X, X, X, X, X, X, X, X, X, X, 1, X, X, 0, 1, 1, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X},
{X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, 1, 0, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X},
{X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, 1, X, 0, 1, 1, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X},
{X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, 1, 0, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X},
{X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, 1, X, 0, 1, 1, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X},
{X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, 1, 0, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X},
{X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, 1, X, 0, 1, 1, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X},
{X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, 1, 0, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X},
{X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, 1, X, 0, 1, 1, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X},
{X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, 1, 0, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X},
{X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, 1, X, 0, 1, 1, 1, X, X, X, X, X, X, X, X, X, X, X, X, X},
{X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, 1, 0, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X},
{X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, 1, X, 0, X, X, X, X, X, X, X, X, X, X, X, X, X, X},
{X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, 1, X, X, 0, 1, 1, X, X, X, X, X, X, X, X, X, X, X},
{X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, 1, 0, X, X, X, X, X, X, X, X, X, X, X, X},
{X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, 1, X, 0, 1, 1, X, X, 1, 1, X, X, X, X, X},
{X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, 1, 0, X, X, X, X, X, X, X, X, X, X},
{X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, 1, X, 0, 1, 1, X, X, X, X, X, X, X},
{X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, 1, 0, X, X, X, X, X, X, X, X},
{X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, 1, X, 0, X, X, X, X, X, X, X},
{X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, 1, X, X, X, X, 0, 1, X, X, X, X, X},
{X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, 1, X, X, X, X, 1, 0, 1, X, X, X, X},
{X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, 1, 0, 1, 1, X, X},
{X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, 1, 0, X, X, X},
{X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, 1, X, 0, 1, 1},
{X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, 1, 0, X},
{X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, 1, X, 0}};
lista = new ArrayList<Integer>();
System.out.println("Main Matrix.");
printMatrix(M);
System.out.println("Shortest Path Matrix.");
printMatrix(FloydAlgo(M));
addDrawPointsToList(3, 12);
printList(lista);
}
public static List addDrawPointsToList(int a, int b, int[][] M) {
return lista;
}
public static int[][] FloydAlgo(int[][] M) {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
for (int k = 0; k < N; k++) {
// to keep track.;
if (M[j][i] + M[i][k] < M[j][k]) {
M[j][k] = M[j][i] + M[i][k];
}
}
}
}
return M;
}
public static void printMatrix(int[][] Matrix) {
System.out.print("\n\t");
for (int j = 0; j < N; j++) {
System.out.print(j + "\t");
}
System.out.println();
for (int j = 0; j < 347; j++) {
System.out.print("-");
}
System.out.println();
for (int i = 0; i < N; i++) {
System.out.print(i + " |\t");
for (int j = 0; j < N; j++) {
if (Matrix[i][j] == 999) {
System.out.print("X");
} else {
System.out.print(Matrix[i][j]);
}
System.out.print("\t");
}
System.out.println("");
}
System.out.println("\n");
}
public static void printIntArray(int A[]) {
for (int i = 0; i < N; i++) {
System.out.print(A[i] + " ");
}
}
public static void printList(List L) {
for (int i = 0; i < L.size(); i++) {
System.out.print(L.get(i) + ", ");
}
System.out.println("\nList size: " + L.size());
}}
我覺得這可能是一個有待解決的小問題,但我是一個新手程序員,我沒有看到解決方案。我會很感激任何建議。 Sry for my english; <
這是一個無法解決或太容易說我真正的解決方案嗎? – CulE