Jung API中最短路径算法的性能

Question

我使用荣格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中是否有其他算法？使用另一个图形实现，该实现为最短路径提供更多不同的方法吗？

到目前为止，谢谢:)

Answer 1

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代码搜索中获取它。