Code Verständnisfragen - FLoyd Warshall Algorithmus

[bob651]

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:

//     * 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

 

[Viktim]

Da fehlen ein Paar Felder...