Реализация алгоритма Дейкстры в Java

Question

Я много читал об этом и знаю, что дискуссии об этом алгоритме в Java встречались редко. Моя проблема с реализацией алгоритма Дейкстры в Java заключается в том, что я просто не знаю, как подготовить свои данные.

У меня есть набор координат в массиве и набор 1 и 0 в матрице, которые представляют, есть ли путь между точками, которые представляют координаты. Мой вопрос: как мне представить эту информацию, чтобы я мог найти лучший путь с Dijkstra? Я видел, как многие люди создавали класс «Узел», но, похоже, они никогда не сохраняют координаты в этом Узле. Есть ли какой-то стандартизированный способ создания такого рода структуры (я полагаю, что это график?), Который мне просто не хватает?

Любая помощь будет оценена.

Answer 1

Есть два основных варианта: 1. Вы можете использовать матрицу смежности, в которой строки и столбцы представляют ваши узлы. Матрица значений [x, y] должна быть весом (например, расстояние / стоимость и т. Д.) Для перемещения от x к y. Вы можете использовать евклидово расстояние для вычисления этих значений из вашего массива координат; 2. Вы можете реализовать пару классов (Node, Edge - или просто Node с внутренней картой для другого узла и весом в качестве значения карты) - это действительно график.