Производительность алгоритма кратчайшего пути в JUNG API - PullRequest
Новая
       18

Производительность алгоритма кратчайшего пути в JUNG API

1 голос
/ 28 июня 2010

Я использую JUNG API для вычисления кратчайших путей между несколькими узлами в средних больших графах (от 20 до 100 узлов). Сейчас я перебираю свои узлы и использую простую функцию ShortetsPath для вычисления кратчайшего пути для двух узлов. Все кратчайшие пути помещаются в ArrayList. 

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);
}

}

Я хотел бы ускорить вычисления, потому что мне нужно вычислить это для многих графиков и узлов. Насколько я знаю, только Dijkstra доступен в JUNG API. Итак, мои вопросы: могу ли я использовать Dijkstra для повышения производительности? Доступны ли другие алгоритмы в JUNG API? Имеет ли смысл использовать другую реализацию графа, которая предлагает более различные методы для кратчайших путей?

Пока спасибо:)

1 Ответ

1 голос
/ 28 июня 2010

Класс UnweightedShortestPath в JUNG использует алгоритм поиска в ширину, который имеет O (n ^ 2) времени выполнения. Алгоритм Дейкстры работает по существу так же, только для взвешенных графов вместо невзвешенных графов, поэтому его время выполнения также равно O (n ^ 2).

Тем не менее, похоже, что вас интересуют расстояния между всеми возможными парами узлов в вашем графике, но вы используете парный подход. Таким образом, ваше общее время выполнения O (n * n ^ 2) = O (n ^ 3). Вместо этого вы можете использовать глобальный алгоритм кратчайшего пути, такой как алгоритм Джонсона (http://en.wikipedia.org/wiki/Johnson's_algorithm). Это время выполнения O (n ^ 2 * log (n + ne)). Так что в целом немного быстрее.

Насколько я знаю, он не реализован в JUNG, но, возможно, вам удастся воспользоваться поиском по коду Google.

...