#shortest-path #jgraph
Вопрос:
Java получает кратчайший путь между всеми вершинами сложной сети. Если число вершин очень велико, использование JGraph для получения всех вершин в двухслойном цикле неэффективно. Как повысить эффективность?
Set<V> vs = graph.vertexSet();
List<GraphPath<V, E>> list = new ArrayList<>();
for (V v : vs) {
for (V v1 : vs) {
if (!v.equals(v1)) {
GraphPath<V, E> path = floydWarshallShortestPaths.getPath(v, v1);
list.add(path);
}
}
}
Комментарии:
1. Алгоритм Флойда-Уоршалла вычисляет все кратчайшие пути в графике за O(n^3) времени. Это та реализация, которую вы используете? Если это так, вы можете просто позвонить
getPaths()в каждую вершину. Независимо от этого, реализация должна просто выполнить расчет один раз.