#java #algorithm #graph-theory #shortest-path
#java #алгоритм #теория графов #кратчайший путь
Вопрос:
Мне нужно найти кратчайший путь сверху слева направо.
Правила таковы, что он должен проходить от A до B, от A до B и т.д.
Смотрите картинку в качестве примера:
Тогда ожидаемый результат для приведенного выше рисунка равен 13.
Я пытаюсь реализовать это на java с помощью алгоритма дейкстры для этого, но затем застрял. Правильный ли это путь?
Комментарии:
1. Нужно ли это реализовывать поверх изображения? @David
2. Алгоритм Дейсктры наверняка является одним из способов решения проблемы (другим возможным алгоритмом может быть A * ). Вы должны сказать нам, где именно вы застряли (если это проблема с кодом, тогда покажите код, который у вас есть на данный момент), но я предполагаю, что это связано с расположением графика. В принципе, вы могли бы предположить, что если две соседние ячейки имеют одинаковое значение, то между ними есть «стена», поэтому ребра графика могут находиться только между соседними ячейками с разными значениями.
3. Я пытаюсь реализовать это на Java
4. Просто реализуйте алгоритм A *.
5. Итак, что вы пробовали? Существует много страниц, посвященных этой теме. baeldung.com/java-dijkstra
Ответ №1:
Если цель состоит в том, чтобы найти кратчайший путь из верхнего левого угла в нижний правый угол (или между любыми произвольными 2 точками), dijsktra является одним из возможных способов, однако вы должны правильно построить график из входных данных.
В этом случае я бы выбрал простой flood-fill алгоритм. Вы можете найти несколько онлайн-ресурсов, объясняющих это, включая это видео или эту статью, поэтому я не буду вдаваться в подробности в этом ответе.
Вы можете найти кратчайший маршрут, используя только 2 матрицы (одна для вашего исходного массива букв и одна для расстояний), если вы правильно реализуете свои правила (только от A до B и от B до A).
Ответ №2:
Вы можете использовать любой алгоритм обхода графа или любой алгоритм поиска пути. Итак, здесь много алгоритмов, таких как A *, Dijekstra, BFS, DFS …
Для примера давайте возьмем BFS, которая находит кратчайший путь между 2 узлами графика. Предположим, ваш 2d-массив представляет собой график, где ребра находятся при условии, что расстояние между 2 узлами равно 1 и один из узлов равен A, а второй — B. Режим чтения о BFS здесь (https://en.wikipedia.org/wiki/Breadth-first_search )
Просто постройте график из вашей матрицы и реализуйте BFS для графика, или вы можете просто реализовать BFS для массива.