如何找到两个最广泛分离的节点之间的距离

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

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

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).

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

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

现在,我确实有以下形式的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;
}

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.

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

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?

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

Here is a sample input for the problem:

以下是问题的示例输入:

Total Nodes: 5

总节点:5

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

边缘:节点2 - 连接 - 节点4.距离/重量25节点2 - 连接 - 节点5.距离/重量26节点3 - 连接 - 节点4.距离/重量16节点1 - 连接 - 节点4.距离/重量14

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

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

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

那么我应该如何描述或者是否有更简单且更少计算成本的方式?

6 个解决方案

#1

It looks like you can use either of:

看起来你可以使用以下任何一个:

Floyd Warshall algorithm

Floyd Warshall算法

Johnson's algorithm.

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

我不能给你很多关于他们的指导 - 我不是专家。

#2

So there's an implementation of Dijkstra which runs O(VlogV + E) giving your approach a complexity of roughly V^2logV + VE. See DADS. But perhaps more intuitive would be to run one of the all pairs shortest path algorithms like Floyd-Warshall or Johnsons. Unfortunately they're all roughly O(V^3) for dense graphs (close to the complete graph where E = V^2).

所以Dijkstra的实现运行O(VlogV + E),使您的方法具有大致V ^ 2logV + VE的复杂性。见DADS。但也许更直观的是运行像Floyd-Warshall或Johnsons这样的所有对最短路径算法之一。不幸的是,对于密集图,它们都大致为O(V ^ 3)(接近E = V ^ 2的完整图)。

#3

Is this the Roads in the North problem?

这是北方的道路问题吗?

#4

You can use your Dijkstra's implementation as follows:

您可以使用Dijkstra的实现,如下所示:

Pick a random node,(a), run Dijkstra from node a, and find the furthest node from it. Mark that node as node b.

选择一个随机节点,(a),从节点a运行Dijkstra,并从中找到最远的节点。将该节点标记为节点b。

Run Dijkstra again starting at node b, and find the furthest node from it. Mark that node as node c.

从节点b开始再次运行Dijkstra,并从中找到最远的节点。将该节点标记为节点c。

I don't have proof for this, but I think b and c will be furthest away nodes. You might need to run one more iteration (I'm still thinking about it).

我没有这方面的证据,但我认为b和c将是最远的节点。您可能需要再运行一次(我还在考虑它)。

#5

Multiply the edge weights by -1 and find the shortest path on the new graph. That would be the longest path on the original graph

将边权重乘以-1,找到新图上的最短路径。这将是原始图表上最长的路径

#6

If you want the longest shortest path that is

如果你想要最长的最短路径

sup i,j {inf i,j {n : n=length of a path between i and j}}

sup i,j {inf i,j {n:n = i和j之间路径的长度}}

you should certainly consider a all nodes shortest path algorithm like Flyod-Warshall as mentioned by others. This would be in the order of O(V^3).

你应该考虑像其他人提到的所有节点最短路径算法,如Flyod-Warshall。这将是O(V ^ 3)的量级。

If you want the longest possible path that is

如果你想要尽可能长的路径

sup i,j {n : n=length of a path between i and j}

sup i,j {n:n = i和j之间路径的长度}

you could try to use Midhat's idea. (which really is as complex as the original problem as pointed out in the comments) I would recommend to invert the weights with 1/w though, to retain positive weights, given the original weights were strict positive.

你可以尝试使用Midhat的想法。 (这实际上和评论中指出的原始问题一样复杂)我会建议用1 / w来反转权重,以保持正权重,因为原始权重是严格的正数。

Another algorithm you might want to look up when dealing with negative weights is the algorithm of Bellman and Ford

在处理负权重时,您可能想要查找的另一种算法是Bellman和Ford的算法

#1