Реконструкция пути Флойда-Уоршалла без рекурсии

Я использую этот алгоритм Флойда-Уоршалла из здесь.

import static java.lang.String.format;
import java.util.Arrays;



public class FloydWarshall {


    public static void main(String[] args) {
        int[][] weights = {{1, 3, -2}, {2, 1, 4}, {2, 3, 3}, {3, 4, 2}, {4, 2, -1}};
        int numVertices = 4;

        floydWarshall(weights, numVertices);
    }

    static void floydWarshall(int[][] weights, int numVertices) {

        double[][] dist = new double[numVertices][numVertices];
        for (double[] row : dist)
            Arrays.fill(row, Double.POSITIVE_INFINITY);

        for (int[] w : weights)
            dist[w[0] - 1][w[1] - 1] = w[2];

        int[][] next = new int[numVertices][numVertices];
        for (int i = 0; i < next.length; i++) {
            for (int j = 0; j < next.length; j++)
                if (i != j)
                    next[i][j] = j + 1;
        }

        for (int k = 0; k < numVertices; k++)
            for (int i = 0; i < numVertices; i++)
                for (int j = 0; j < numVertices; j++)
                    if (dist[i][k] + dist[k][j] < dist[i][j]) {
                        dist[i][j] = dist[i][k] + dist[k][j];
                        next[i][j] = next[i][k];
                    }

        printResult(dist, next);
    }

    static void printResult(double[][] dist, int[][] next) {
        System.out.println("pair     dist    path");
        for (int i = 0; i < next.length; i++) {
            for (int j = 0; j < next.length; j++) {
                if (i != j) {
                    int u = i + 1;
                    int v = j + 1;
                    String path = format("%d -> %d    %2d     %s", u, v,
                            (int) dist[i][j], u);
                    do {
                        u = next[u - 1][v - 1];
                        path += " -> " + u;
                    } while (u != v);
                    System.out.println(path);
                }
            }
        }
    }
}

Сам алгоритм вполне ясен, но что я не понимаю, так это матрицу next. Насколько я понимаю, индексы i,j должны быть последним предшествующим узлом на пути от узла i к узлу j. Затем путь печати печатается рекурсивно. Но этот фрагмент кода использует какой-то другой подход в операторе печати printResult. Так вот у меня вопрос, что именно за матрица next и как работает печать?


java algorithm floyd-warshall
person fishysushi    schedule 24.05.2018    source источник

Ответы (1)


arrow_upward
0
arrow_downward

строка dist[i][j] = dist[i][k] + dist[k][j] говорит: при переходе от i к j пройдите k, выбрав кратчайший путь от i до k, а затем кратчайший путь от k до j. Здесь: next[i][j] = next[i][k] говорится, что при переходе от i к j сначала идите туда, куда бы вы пошли, если бы вы шли от i к k.

Итак, строка u = next[u - 1][v - 1]; говорит: u теперь следующий узел на пути от u до v.

person maniek    schedule 25.05.2018