Мне нужна помощь, чтобы реализовать все пары алгоритма кратчайшего пути в коде

Question

Я бы действительно, если бы кто-то мог помочь реализовать следующий алгоритм в следующем java коде, я также добавил бы график и пример вывода. [Java код извините, что не позволил бы мне опубликовать] [https://i.stack.imgur.com/meipB.png] [Алгоритм} [https://i.stack.imgur.com/pE6Pv.png] [График] [https://i.stack.imgur.com/WnSFk.png] [Вывод] [https://i.stack.imgur.com/Mpdoz.png] [Вывод] [https://i.stack.imgur.com/geBJP.png]

Answer 1

Здесь я разместил реализованный алгоритм, который, кажется, не дает правильных значений L [], необходимых для печати вершин. Пожалуйста, посмотрите, если алгоритм верен или нет, прежде чем я не смогу продолжить.

    public class Graph {

    public static void main(String[] args) {

        int[][] W = new int[][] { { 0, 2, Integer.MAX_VALUE, 2 }, { 0, 0, Integer.MAX_VALUE, 2 },
                { 1, -1, 0, Integer.MAX_VALUE }, { Integer.MAX_VALUE, -1, -1, 0 } };

        int[][] result = APSP1(W);

        display(4, result);
    }

    /**
     * @param w
     * @return
     */
    private static int[][] APSP1(int[][] w) {
        int n = w.length;
        LinkedList<int[][]> L = new LinkedList<int[][]>();
        L.add(w.clone());

//      display(1, L.get(0));

        for (int i = 1; i < n - 1; i++) {
            display(i, L.get(i-1));
            L.add(Extend(L.get(i - 1), w));
        }
        return L.get(n - 2);
    }

    /**
     * @param i
     * @param integers
     */
    private static void display(int i, int[][] arr) {
        System.out.println("L" + i);
        for (int[] ar : arr) {
            for (int a : ar) {
                if (a == Integer.MAX_VALUE) {
                    System.out.print(" ~ ");
                } else {
                    System.out.print(" " + a + " ");
                }
            }
            System.out.println();
        }

        System.out.println();
    }

    /**
     * @param integers
     * @param w
     * @return
     */
    private static int[][] Extend(int[][] l, int[][] w) {
        int n = l.length;
        int[][] l$ = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                l$[i][j] = Integer.MAX_VALUE;
                for (int k = 0; k < n; k++) {
                    int n2;
                    if (l[i][k] == Integer.MAX_VALUE || w[k][j] == Integer.MAX_VALUE) {
                        n2 = Integer.MAX_VALUE;
                    } else {
                        n2 = l[i][k] + w[k][j];
                    }
                    l$[i][j] = min(l[i][j], n2);
                }

            }
        }

        return l$;
    }

    /**
     * @param integer
     * @param i
     * @return
     */
    private static int min(int n1, int n2) {
        if (n1== Integer.MAX_VALUE && n2 == Integer.MAX_VALUE) {
            return Integer.MAX_VALUE;
        }
        if (n1 >= Integer.MAX_VALUE) {
            return n2;
        }
        if (n2 >= Integer.MAX_VALUE) {
            return n1;
        }
        return n1 < n2 ? n1 : n2;
    }

}

На вашем изображении geBJP показано ABD C как кратчайший путь [от A -> C] A -> (2) -> B -> (2) -> D -> (- 1) -> C общая стоимость = 3, но на графике A -> (2) -> D -> (- 1) -> C - кратчайший путь со стоимостью = 1