1

我使用 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);
}

}

我想加快计算速度，因为我必须为许多图形和节点计算这个。据我所知，JUNG API 中只有 Dijkstra 可用。所以我的问题是：我可以使用 Dijkstra 来提高性能吗？JUNG API 中是否有其他算法可用？使用另一个为最短路径提供更多不同方法的图形实现是否有意义？

到目前为止感谢:)

4

1 回答 1

1

JUNG 中的 UnweightedShortestPath 类使用广度优先搜索算法，它的运行时间为 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 中实现，但你可以从谷歌代码搜索中获取它。

于 2010-06-28T13:24:11.617 回答