如何找到两个相距最远的结点之间的距离

Question

我正在解决前几年的ACM编程竞赛问题，试图更好地解决Graph问题。

我现在正在做的是，我得到了任意数量的无向图节点，它们的邻居以及连接这些节点的边的距离。我需要的是两个最远的节点之间的距离(权重距离，而不是节点的距离)。

现在，我有Dijkstra的算法，它的形式是：

// Dijkstra's Single-Source Algorithm
private int cheapest(double[] distances, boolean[] visited)
{
        int best = -1;
        for (int i = 0; i < size(); i++)
        {
                if (!visited[i] && ((best < 0) || (distances[i] < distances[best])))
                {
                        best = i;
                }
        }
        return best;
}

// Dijkstra's Continued
public double[] distancesFrom(int source)
{
        double[] result = new double[size()];
        java.util.Arrays.fill(result, Double.POSITIVE_INFINITY);
        result[source] = 0; // zero distance from itself
        boolean[] visited = new boolean[size()];
        for (int i = 0; i < size(); i++)
        {
                int node = cheapest(result, visited);
                visited[node] = true;
                for (int j = 0; j < size(); j++)
                {
                        result[j] = Math.min(result[j], result[node] + getCost(node, j));
                }

        }
        return result;
}

有了这个实现，我可以给它一个特定的节点，它将给我一个到该节点的所有距离的列表。因此，我可以获取距离列表中最大的距离，但我不能确定任何特定的节点都是两端最远的两个节点之一。

所以我能想到的唯一解决方案就是在每个节点上运行Dijkstra算法，遍历每个返回的距离列表，寻找最大的距离。在穷尽每个节点返回它的距离列表之后，我应该得到任意两个节点之间的最大距离的值(两个最相隔最远的村庄之间的“道路”距离)。必须有一种更简单的方法来做到这一点，因为这似乎在计算上非常昂贵。问题是可能有多达500个节点的样本输入，所以我不希望花费太长时间。这是我应该做的吗？

以下是该问题的示例输入：

总节点数:5

边缘：

节点2-连接-节点4.距离/权重25

节点2-连接-节点5.距离/权重26

节点3-连接-节点4.距离/权重16

节点1-连接-节点4.距离/权重14

这个样本输入的答案是"67英里“。这是两个相隔最远的村庄之间的道路长度。

那么，我应该按照我所描述的方式来做吗?或者有没有一种更简单、计算成本更低的方法？

Answer 1

看起来您可以使用以下两种方法之一：

• Floyd Warshall algorithm
• Johnson's algorithm.

不过，我不能给你太多的指导--我不是专家。

Answer 2

所以有一个Dijkstra的实现，它运行O(VlogV + E)，给你的方法带来了大约V^2logV + VE的复杂性。参见DADS。但也许更直观的是运行全pairs shortest path算法中的一种，比如弗洛伊德-沃肖或约翰逊。不幸的是，对于密集图(接近于E=V^2的完整图)，它们大致都是O(V^3)。

Answer 3

这是Roads in the North的问题吗？