Jung API中最短路径算法的性能
-
01-10-2019 - |
题
我使用荣格API计算中等大图(20至100个节点)中几个节点之间的最短路径。现在,我在节点上迭代,并使用简单的“ Shortetspath”功能来计算两个节点的最短路径。所有最短的路径都放在阵列列表中。
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提高性能吗? Jung API中是否有其他算法?使用另一个图形实现,该实现为最短路径提供更多不同的方法吗?
到目前为止,谢谢:)
解决方案
Jung中的未加权ShortestPath类使用具有O(n^2)运行时的广度优先搜索算法。 Dijkstra算法基本相同,仅用于加权图而不是未加权图,因此运行时也是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代码搜索中获取它。
不隶属于 StackOverflow