#java #shortest-path #jgrapht
Вопрос:
Теперь существует очень большая сеть неориентированных графов, я хочу вычислить кратчайший путь между всеми вершинами неориентированного графа, но эффективность очень низкая, могу ли я разделить и объединить неориентированный граф? В настоящее время используется библиотека Java jgrapht. В настоящее время количество вершин составляет 8000 , а потребление памяти и времени вычисления очень серьезно.
DijkstraManyToManyShortestPaths<V, E> manyShortestPaths = new DijkstraManyToManyShortestPaths<>(graph);
ManyToManyShortestPathsAlgorithm.ManyToManyShortestPaths<V, E> shortestPaths = manyShortestPaths.getManyToManyPaths(vs, vs);
Комментарии:
1. Простое упоминание количества вершин не очень полезно: вычисление кратчайшего пути на графике с 8000 вершинами и без ребер-довольно простая задача :). В зависимости от количества ребер (плотный или разреженный график) вам может потребоваться выбрать другой алгоритм.
Ответ №1:
Используя JGraphT, вы можете попробовать следующие 2 различных алгоритма:
- ContractionHierarchyBidirectionalDijkstra, который опирается на иерархии сокращений
- TransitNodeRoutingShortestPath, который использует транзитные узлы
Оба алгоритма требуют изрядного объема предварительных вычислений. Но как только предварительное вычисление завершается, выполнение запросов по кратчайшему пути становится дешевым. Вы можете попробовать и то, и другое, так как они реализуют один и тот же интерфейс кратчайшего пути.
Для дальнейшей оптимизации хранения памяти вы также можете ознакомиться с некоторыми специализированными структурами графических данных в пакете jgrapht-opt.
Комментарии:
1. Спасибо вам за ваш ответ! Это плотный график, можете ли вы привести примеры кода?