如何找到两个最广泛分离的节点之间的距离 [英] How to find the distance between the two most widely separated nodes

问题描述

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

I'm working through previous years ACM Programming Competition problems trying to get better at solving Graph problems.

我现在正在研究的是我给出了任意数量的无向图节点，它们的邻居以及连接节点的边缘的距离。我需要的是距离彼此最远的两个节点之间的距离（重量距离，而不是距节点数＃）。

The one I'm working on now is I'm given an arbitrary number of undirected graph nodes, their neighbors and the distances for the edges connecting the nodes. What I NEED is the distance between the two farthest nodes from eachother (the weight distance, not by # of nodes away).

现在，我确实有Dijkstra的算法形式：

Now, I do have Dijkstra's algorithm in the form of:

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

通过这个实现，我可以给它一个特定的节点，它会给我一个该节点的所有距离列表。所以，我可以抓住距离列表中的最大距离，但我无法确定任何特定节点是两端最远的两个节点之一。

With this implementation I can give it a particular node and it will give me a list of all the distances from that node. So, I could grab the largest distance in that list of distances but I can't be sure that any particular node is one of the two furthest ones at either end.

所以我能想到的唯一解决办法是在每个节点上运行这个Dijkstra算法，遍历每个返回的距离列表并寻找最大距离。在耗尽每个节点返回它的距离列表后，我应该得到任意两个节点之间最大距离的值（两个最广泛分隔的村庄之间的道路距离）。必须有一种更简单的方法来执行此操作，因为这看起来实际上非常昂贵。问题是可能有多达500个节点的样本输入，所以我不希望它花费太长时间。这是我应该怎么做的？

So the only solution I can think of is to run this Dijkstra's algorithm on every node, go through each returned list of distances and looking for the largest distance. After exhausting each node returning it's list of distances I should have the value of the largest distance between any two nodes (the "road" distance between the two most widely seperated villages). There has got to be an easier way to do this because this seems really computationally expensive. The problem says that there could be sample inputs with up to 500 nodes so I wouldn't want it to take prohibitively long. Is this how I should do it?

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

Here is a sample input for the problem:

总节点数： 5

边缘：

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

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

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

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

Edges:
Nodes 2 - Connect - Node 4. Distance/Weight 25
Nodes 2 - Connect - Node 5. Distance/Weight 26
Nodes 3 - Connect - Node 4. Distance/Weight 16
Nodes 1 - Connect - Node 4. Distance/Weight 14

此示例输入的答案是67英里。这是两个分布最广的村庄之间的道路长度。

The answer to this sample input is "67 miles". Which is the length of the road between the two most widely separated villages.

我应该如何描述，或者是否有更简单，更便宜的计算方式？

So should I do it how I described or is there a much simpler and much less computationally expensive way?

推荐答案

看起来你可以使用以下任何一种：

It looks like you can use either of:

• Floyd Warshall算法


• Johnson的算法。

• Floyd Warshall algorithm
• Johnson's algorithm.

虽然我不能给你很多指导 - 我不是专家。

I can't give you much guidance about them though - I'm no expert.

这篇关于如何找到两个最广泛分离的节点之间的距离的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！