Проблемы реализации Флойда-Уоршалла

У меня возникли трудности с реализацией алгоритма Флойда-Уоршалла для собственного проекта, который я пытаюсь понять. У меня есть тестовый набор данных, но когда я распечатываю его после создания ShortestPath, я просто получаю null и адрес памяти. Не знаю точно, куда идти с этим алгоритмом отсюда. Любая помощь приветствуется!

public static void main(String[] args) {
    int x = Integer.MAX_VALUE;
    int[][] adj = {{ 0, 3, 8, x, 4 },
                   { x, 0, x, 1, 7 },
                   { x, 4, 0, x, x },
                   { 2, x, 5, 0, x },
                   { x, x, x, 6, 0 }};
    ShortestPath sp = new ShortestPath(adj);
    System.out.println(sp);
}

public class ShortestPath {

private int[][] adj;
private int[][] spTable;
private int n;

public static void copy(int[][] a, int[][] b) {
    for (int i=0; i < a.length; i++)
        for (int j = 0; j < a[0].length; j++)
            a[i][j] = b[i][j];
}

public ShortestPath(int[][] adj) {
    n = adj.length;
    this.spTable = new int[n][n];
    copy(this.spTable, adj);

    for(int k = 0; k < n; k++) {
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                if (spTable[i][k] + spTable[k][j] < spTable[i][j]) {
                    spTable[i][j] = spTable[i][k] + spTable[k][j];
                    adj[i][j] = adj[k][j];
                }
            }
        }
    }
}


@Override
public String toString() {
    return adj + "\n\n" + spTable + "";
}

person John Goodman    schedule 03.11.2013    source источник


Ответы (1)


public ShortestPath(int[][] adj)

Параметр adj, который вы передаете здесь, затеняет вашего члена класса adj — вы никогда не даете члену класса значение. Простое исправление состоит в том, чтобы поместить следующую строку кода в любое место в приведенном выше конструкторе:

this.adj = adj;

См. это для получения дополнительной информации.


Другая проблема здесь:

return adj + "\n\n" + spTable + "";

Вы не можете напечатать значения в массиве, просто добавив его в строку — это просто напечатает адрес.

Вам нужен двойной цикл для печати значений в массиве. Дополнительные сведения см. в этом вопросе.

person Bernhard Barker    schedule 04.11.2013