Выполнение кратчайшего алгоритма пути в Jung API
-
01-10-2019 - |
Вопрос
Я использую API JUNG, чтобы рассчитать кратчайшие пути между несколькими узлами в средних больших графах (от 20 до 100 узлов). Прямо сейчас я итарируюсь по моим узлам и использую простую функцию «ShortetPath» для расчета кратчайшего пути для двух узлов. Все самые короткие пути помещают в арарилист.
UnweightedShortestPath<Vertex, SEdge> dist = new UnweightedShortestPath<Vertex, SEdge>(undir);
ArrayList<Vertex> tv = new ArrayList<Vertex>(); // contains nodes for shortestpath
ArrayList<Integer> distances = new ArrayList<Integer>(); // for the distances
for (int j = 0; j <tv.size()-1;j++){ //iterate over nodes
Vertex one = tv.get(j);
for (int k = j+1; k<tv.size();k++){ //iterate over next nodes
Vertex two = tv.get(k);
Number n = dist.getDistance(one, two);
int d;
if (n == null) {
d = 5000000;
}
else {
d = n.intValue();
}
distances.add(d);
}
}
Я хотел бы ускорить расчет, потому что я должен рассчитать это для многих графиков и узлов. Насколько я знаю, в Jung API доступен только Dijkstra. Итак, мои вопросы: Могу ли я использовать Dijkstra для повышения производительности? Доступны ли другие алгоритмы в API Jung? Это имеет смысл использовать другую реализацию графика, которая предлагает более разные методы для кратчайших путей?
Спасибо до сих пор :)
Решение
Класс undweightedshortshortspath в Jung использует алгоритм сначала поиска в ширину, который имеет o (n ^ 2) время выполнения. Алгоритм Dijkstra работает по существу одинаково, просто для взвешенных графиков вместо невзвешенных графиков, поэтому это время выполнения также является o (n ^ 2).
Тем не менее, похоже, что вы заинтересованы в расстояниях между всеми возможными парами узлов в вашем графике, но вы используете парный подход. Таким образом, ваше полное время выполнения равно (N * N ^ 2) = O (n ^ 3). Вместо этого вы можете использовать глобальный кратчайший алгоритм пути, как алгоритм Джонсона (http://en.wikipedia.org/wiki/johnson's_algorithm). Это время выполнения o (n ^ 2 * log (n + ne)). Так что немного быстрее в целом.
Он не реализован в Юге, насколько я знаю, но вы сможете справиться с поиском кода Google.