Hi,
ich habe hier einen Code und muss ihn bald erklären. Ich habe es soweit wie möglich kommentiert, aber verstehe die einzelnen Schritte nicht. Könnt ihr eventuell die Methoden etwas genauer kommentieren ?
Hier ist der Code:
MfG
ich habe hier einen Code und muss ihn bald erklären. Ich habe es soweit wie möglich kommentiert, aber verstehe die einzelnen Schritte nicht. Könnt ihr eventuell die Methoden etwas genauer kommentieren ?
Hier ist der Code:
Code:
// * Floyd-Warshall Algorithmus zum bestimmen des kürzesten Weges und des Vorgängers
// *
// * @param G - der zu untersuchende Graph
// * gibt false zurück, wenn es negativen zyklus hat, sonst gibt er true zurück
// *
// * Aktion - vorgänger/distanzmatrix bestimmen und zeigt sie
// *
//
static boolean floydalgorithmus(Integer[][] G) {
// Knoten-ID mit 0,...,n indizieren
HashSet<Integer> vertexIds = new HashSet<Integer>();
// Knoten-ID sammeln
for (Integer[] reihe : G) {
if (reihe == G[0]) continue;
vertexIds.add(reihe[0]);
vertexIds.add(reihe[1]);
}
// Knoten-IDs aufsteigend sortieren
Object[] sort0 = vertexIds.toArray();
int[] sortie = new int[sort0.length];
for (int i = 0; i < sortie.length; i++) {
sortie[i] = (int) sort0[i];
}
MergeSort.mergesort(sortie, 0, sortie.length - 1);
// Knoten IDs bezeichnen von 0 ...n
for (int i = 0; i < vertexIds.size(); i++) {
for (Integer[] reihe : G) {
if (reihe[0] == sortie[i]) reihe[0] = i;
if (reihe[1] == sortie[i]) reihe[1] = i;
}
}
//danach--> Jetzt von 0,...,vertexIds.size()-1
// Distanz/Vorganger-Matrix mit MAX_VALUE / null initialisieren
DISTANZ = new double [G[0][0]][G[0][0]];
VORGANGER = new Integer[G[0][0]][G[0][0]];
for (int i = 0; i < DISTANZ.length; i++) {
for (int j = 0; j < DISTANZ[i].length; j++) {
DISTANZ[i][j] = Double.MAX_VALUE;
VORGANGER[i][j] = null;
}
}
// Vorgaenger/ Distanzen löschen ausm Graphen
for (int i = 1; i < G.length; i++) {
DISTANZ[G[i][0]][G[i][1]] = G[i][2];
VORGANGER[G[i][0]][G[i][1]] = G[i][0];
}
// IDs zurück benennen
for (Integer i = 0; i < vertexIds.size(); i++) {
for (Integer[] reihe : G) {
if (reihe[0] == i) reihe[0] = sortie[i];
if (reihe[1] == i) reihe[1] = sortie[i];
}
for (Integer[] reihe : VORGANGER) {
for (Integer j = 0; j < reihe.length; j++) {
if (reihe[j] == i) reihe[j] = sortie[i];
}
}
}
// IDs haben jetzt alten Namen
// Ausgabe der Graphen / Distanz / VorgaangerMatrix
zeichnegraph(G);
System.out.println("\n");
System.out.println("Ursprungsmatrizen: \n");
printDISTANZ(DISTANZ);
System.out.println();
printVORGANGER(VORGANGER);
System.out.println();
// Hauptaufgabe -->Distanz/ Vorgaenger-Matrix bestimmen
for (int k = 0; k < DISTANZ.length; k++) {
for (int i = 0; i < DISTANZ.length; i++) {
for (int j = 0; j < DISTANZ.length; j++) {
if (DISTANZ[i][j] > DISTANZ[i][k] + DISTANZ[k][j]) {
DISTANZ[i][j] = DISTANZ[i][k] + DISTANZ[k][j];
VORGANGER[i][j] = VORGANGER[k][j];
}
}
}
// Fehlermeldung wenn Zyklus negativ ist
if (DISTANZ[k][k] < 0.0) {
System.out.println("Negativer Zyklus");
return false;
}
}
// Ausgabe End- Distanz/Vorgaenger
System.out.println("Endmatrizen \n");
System.out.println("XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX");
printDISTANZ(DISTANZ);
System.out.println();
printVORGANGER(VORGANGER);
System.out.println();
return true;
}
MfG