Реализация алгоритма Флойда-Уоршалла со списком списков

Я хочу использовать алгоритм Флойда-Уоршалла, чтобы найти кратчайший путь между двумя вершинами. Матрица находится в списке ArrayList ‹ArrayList ‹Integer››. Он всегда довольно маленький, например, матрица 4х4 или 8х8.

В моем классе уже есть матрица расстояний. Я просто пытаюсь создать матрицу «кратчайшего пути». Но это не работает. Он неправильно заполняет мою матрицу.

Я очень надеюсь, что кто-нибудь сможет взглянуть на это и объяснить, что не так.

Моя матрица расстояний:

 0   0  256 411
556  0  558  0
250  0   0  431
 0   0  431  0

Результат теста:

 0   0   0   0 
556 556 556 556 
250 250 250 250 
 0   0   0   0

Ожидал:

500 0 842 681
556 0 806 967
 0  0 500 681
581 0  0  862

Я закомментировал свой тестовый результат. distance - моя матрица с целочисленным значением расстояний между вершинами. В моей матрице i - это y, а j - это x.

public ArrayList<ArrayList<Integer>> calcShortest() {
        //String test = "";
        ArrayList<ArrayList<Integer>> shortest = distance;

        for (int k = 0; k < airports.size(); k++) {
            for (int i = 0; i < airports.size(); i++) {
                for (int j = 0; j < airports.size(); j++) {
                    shortest.get(j).add(i, Math.min(shortest.get(k).get(i) + shortest.get(j).get(k), 
                            shortest.get(j).get(i)));
                }
            }
        }
        /*for (int j = 0; j < airports.size(); j++) {
            for (int i = 0; i < airports.size(); i++) {
                test += shortest.get(j).get(i) + " ";
            }
            System.out.println(test);
            test = "";
        }*/
        return shortest;
    }

java algorithm matrix floyd-warshall
person paperplan3    schedule 25.08.2015    source источник
comment
Я понятия не имею, что такое алгоритм Флойда Уоршалла, но не могли бы вы рассказать нам, как получить ожидаемую матрицу с помощью основных операций?   -  person Anarki    schedule 25.08.2015
comment
Википедия: алгоритм Флойда-Уоршалла - это алгоритм для поиска кратчайших путей во взвешенном графе, поэтому он будет заполнять кратчайший путь, например, он проверит кратчайший путь от a до c, он найдет его более быстрый переход d instad of b и заполнит кратчайшее расстояние, когда есть доступный путь. Я использую ориентированный граф, поэтому вначале он может выглядеть странно.   -  person paperplan3    schedule 26.08.2015

Ответы (2)


arrow_upward
3
arrow_downward

Есть ряд проблем с вашим кодом и вашими данными.

  • Операция add shortest.get(j).add(i, ...) вставляет элемент в ArrayList. Вы действительно хотите установить значение: shortest.get(j).set(i, ...)

  • Индексы массива неверны. Вы пытаетесь сделать shortest[j][i] = min(shortest[k][i] + shortest[j][k], shortest[j][i]), но Флойд-Уоршалл требует shortest[i][j] = min(shortest[i][k] + shortest[k][j], shortest[i][j]).

  • Ваш ожидаемый результат не имеет смысла. Как может shortest[2][2] быть 500? Мы уже знаем, что это 0. А как вы вычислили, что shortest[3][0] это 581? Невозможно получить 581 из указанной вами матрицы расстояний.

  • Почему в матрице расстояний по диагонали нулевые значения? Например, distance[1][3] равно 0. Значит, расстояние от узла 1 до узла 3 равно 0? Действительно?

  • Почему вы заставляете shortest ссылаться на distance? Поскольку вы изменяете distance, почему бы просто не использовать distance вместо того, чтобы делать вид, что у вас другая матрица с именем shortest? Или вы собирались сделать копию distance?

Приведенный ниже код правильно запускает Floyd-Warshall, потому что он вызывает set для изменения ArrayList и использует правильные индексы. Однако он не дает того, что вы называете «ожидаемым» результатом для вашей матрицы расстояний, потому что, как я объяснил, ваш ожидаемый результат не имеет смысла, а сама матрица расстояний является подозрительной.

  int n = shortest.size();
  for (int k = 0; k < n; k++) { 
    for (int i = 0; i < n; i++) { 
      for (int j = 0; j < n; j++) { 
        shortest.get(i).set(j,
            Math.min(shortest.get(i).get(k) + shortest.get(k).get(j), 
                     shortest.get(i).get(j)));
      } 
    } 
  }
person Michael Laszlo    schedule 25.08.2015
comment
Спасибо за ответ, мне это очень помогло! Я должен был сказать, что это ориентированный граф, так что вы, возможно, сможете перейти от a к b, но не от b к a. Извините за то, что раскрыл это. Я действительно намеревался сделать копию матричного расстояния, поскольку я буду использовать его отдельно, и мне может понадобиться только расстояние после того, как я проверил кратчайший маршрут. Это не решило мою проблему мгновенно, поэтому я снова все проверил. И обнаружил, что я вставил в свою матрицу расстояний 0 instad от БЕСКОНЕЧНОСТИ, поэтому, конечно, это не сработает, когда я проверяю минимум, и у меня везде нули. Спасибо за помощь! - person paperplan3; 26.08.2015

arrow_upward
0
arrow_downward

Попробуй это:

 shortest.get(j).add(i, Math.min(shortest.get(i).get(k) + shortest.get(k).get(j), 
                        shortest.get(i).get(j)));

Или используйте алгоритм Дейкстры

person Paul Wilker Landaeta Flores    schedule 25.08.2015