древовидные карты в JUNG (для алгоритма кратчайшего пути)

Question

После запроса общих советов по алгоритмам кратчайшего пути ( Двухмерное нахождение путевой точки: комбинации WP для перехода от curLocation к targetLocation ), а затем запрос о более конкретной реализации ( Алгоритм кратчайшего пути (например,. Дейкстры) для 500+ путевых точек / узлов? ) Я решил использовать библиотеку JUNG (http://jung.sf.net/).

Моя цель сейчас состоит в том, чтобы получить кратчайший путь из точки А в точку Биспользуя любую комбинацию точек из списка точек (размер ~ 1000), где каждая точка напрямую связана со всеми точками, которые находятся в пределах расстояния x.

Для этого мне нужно настроить древовидную картуЯ считаю, что это список реализаций древовидной карты: http://jung.sourceforge.net/doc/api/edu/uci/ics/jung/graph/class-use/Hypergraph.html#edu.uci.ics.jung.algorithms.shortestpath

Это правильно? Теперь все эти реализации ограничиваются разреженными древовидными картами, но мне нужно создать довольно плотную древовидную карту.

Итак, какую карту дерева я должен использовать в JUNG для достижения своей цели?

Answer 1

Я думаю, что ваша главная цель достижима с помощью JUNG, но ИМХО, вам нужно отфильтровать по вашему заданному расстоянию "х" (я имею в виду все возможные комбинации между узлами).Однако у меня нет опыта использования алгоритмов кратчайшего пути JUNG, за исключением приведенного ниже примера.

В примере графического интерфейса пользователя JUNG Framework 2.x используется алгоритм кратчайшего пути из BFSDistanceLabeler , для которого требуетсяуниверсальный гиперграф .Он применяет расчет на основе расстояния BFS, а не расчет расстояния на основе веса края.Однако это алгоритм поиска в ширину (BFS).

Вы можете обратиться к исходному коду ShortestPathDemo.class в пакете edu.uci.ics.jung.samples. in jung-samples-2.0.1.jar

Лучшую справочную информацию, которую я могу найти для других алгоритмов кратчайшего пути JUNG, можно найти здесь (PDF): www.grotto-networking.com/JUNG/JUNG2-Tutorial.pdf