Поиск кратчайшего пути в графе лабиринта с использованием матрицы смежности

Question

У меня есть некоторые проблемы с решением конкретной проблемы, которая заключается в поиске кратчайшего пути в графе лабиринта. Вероятно, я застрял из-за того, что лабиринт инициализирован четырехмерным массивом вроде adjacent = new boolean[height][width][height][width]; Первая и вторая пары индексов определяют местоположение на графике в строках/столбцах. График выглядит следующим образом:

XXXXXXXXXXXXX 
..........X.X 
X.XXX.XXX.X.X 
X.X.X...X.X.X 
X.X.XXX.XXX.X 
X...X.....X.. 
XXXXXXXXXXXXX 

ArrayList должен иметь расположение вершин на пути, чтобы от начала до конца включительно.

Я уже написал конструктор и метод подключения; однако у меня проблемы с поиском кратчайшего пути. Вот пример того, как я создаю лабиринт графа:

final int edges[][] = {{1, 0, 1, 1}, {1, 1, 1, 2}, {1, 1, 2, 1}, 
       {1, 2, 1, 3}, {1, 3, 1, 4}, {1, 4, 1, 5}, {1, 5, 1, 6}, 
       {1, 5, 2, 5}, {1, 6, 1, 7}, {1, 7, 1, 8}, {1, 8, 1, 9}, 
       {1, 9, 2, 9}, {1, 11, 2, 11}, {2, 1, 3, 1}, {2, 5, 3, 5}, 
       {2, 9, 3, 9}, {2, 11, 3, 11}, {3, 1, 4, 1}, {3, 3, 4, 3}, 
       {3, 5, 3, 6}, {3, 6, 3, 7}, {3, 7, 4, 7}, {3, 11, 4, 11}, 
       {4, 1, 5, 1}, {4, 3, 5, 3}, {4, 7, 5, 7}, {4, 11, 5, 11}, 
       {5, 1, 5, 2}, {5, 2, 5, 3}, {5, 5, 5, 6}, {5, 6, 5, 7}, 
       {5, 7, 5, 8}, {5, 8, 5, 9}, {5, 11, 5, 12}}; 

     MazeGraph maze = new MazeGraph(13, 7); 

     for (int[] edge : edges) 
      maze.connect(new Location(edge[0], edge[1]), new Location(edge[2], edge[3])); 

Answer 1

Прежде всего, это

adjacent = new boolean[height][width][height][width]; 

противоречит с этим:

Первая и вторая пара индексов указать на графике в строках/столбцах.

Это столбец/ряд, а не ряд/столбец.

Dijkstra's algorithm должно быть реализовано для вашей матрицы.

Пусть узел, с которого мы начинаем, называется начальным узлом. Пусть расстояние узла Y - расстояние от начального узла до Y. Алгоритм Дейкстры назначит некоторые начальные значения расстояния и будет попытаться улучшить их шаг за шагом.

1. Присвоить каждый узел предварительного значение расстояния: установить его в ноль для нашего начального узла и к бесконечности для всех других узлов.

2. Задайте начальный узел как текущий. Отметьте все остальные узлы невидимыми. Создайте набор всех невидимых узлов, называемых невидимым множеством.

3. Для текущего узла рассмотрите все его невидимые соседи и вычислите их предварительные расстояния. Сравните недавно рассчитанное предварительное расстояние до текущего назначенного значения и назначьте меньшим. Например, если текущий узел A отмечен расстоянием, а край, соединяющий его с соседним B, имеет длину 2, то расстояние до B (через A) будет равно 6 + 2 = 8. Если B был , ранее отмеченный на расстояние больше 8, затем измените его на 8. В противном случае сохраните текущее значение.

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

5. Если узел назначения был отмечен посетил (при планировании маршрута между двумя конкретными узлами), или если наималейшее предварительное расстояния между узлами в Непосещенных множествах бесконечность (при планирования полного обхода, возникает, когда нет связи между начальным узлом и оставшимися нераскрытыми узлами), а затем остановится. Алгоритм завершен.

6. В противном случае, выберите Непосещенные узел, помеченный с наименьшим предварительным расстоянием, установить его в качестве нового «текущего узла», и перейти обратно к шагу 3.