logo标签列表

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

javaalgorithmgraph-theory
3

我正在解决之前的ACM编程竞赛问题，试图提高解决图问题的能力。

我现在正在解决一个问题，给定任意数量的无向图节点、它们的邻居以及连接节点的边的距离。我需要的是两个最远节点之间的距离（权重距离，而不是节点数）。

现在，我有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英里”。即是两个最广泛分开的村庄之间的道路长度。那么，我应该按照我所描述的方法进行操作，还是有更简单，更少计算的方法呢？
1
你要找的术语是“直径”。 - wnoise
阅读完：http://mathworld.wolfram.com/GraphDiameter.html 后，他们将直径描述为“直径是必须遍历的最大顶点数，以便从一个顶点到另一个顶点旅行时排除回溯、绕路或循环路径的考虑。” - mmcdole
6个回答
3
阅读关于约翰逊算法的维基百科...它只适用于有向图，这是真的吗？ Floyd-Warshall算法看起来会很有效！ - mmcdole
我猜有向图只是无向图的一种特殊情况 - 只需重复每个无向图中的边，然后反转一次。 - 1800 INFORMATION
我认为两种方法都可以，你的原始算法在我这个非专业人士看来似乎是 Johnson 算法的一个变体（因为你没有负权重，所以跳过了重新加权步骤）。 - 1800 INFORMATION
2
所以有一种Dijkstra的实现方式，它可以在O(VlogV + E)的时间内运行，这使得您的方法的复杂度大约为V^2logV + VE。请参见DADS。但更直观的可能是运行其中一个所有pairs shortest path算法，如Floyd-Warshall或Johnsons。不幸的是，对于密集图（接近完全图，其中E = V^2），它们都大约需要O(V^3)的时间。
1
我的数据包上的问题是“北方道路”，但很明显它们是同一个问题。只是措辞略有不同等。 - mmcdole
0

您可以按照以下步骤使用Dijkstra算法：

  1. 随机选择一个节点a，从节点a开始运行Dijkstra算法，并找到距离它最远的节点。将该节点标记为节点b。
  2. 再次从节点b开始运行Dijkstra算法，并找到距离它最远的节点。将该节点标记为节点c。

我没有证据证明这一点，但我认为b和c将是最远的节点。您可能需要再运行一次迭代（我还在考虑中）。

我认为你可以想出一个微不足道的反例。 - 1800 INFORMATION
此外，很容易看出a将与c相同。 - 1800 INFORMATION
当图是有向的时候，a和c可能不相同。 - Daniel Spiewak
这个问题涉及到一个无向图。 - 1800 INFORMATION
即使是有向图，我脑海中也有一个微不足道的反例 - 不过它太长了，无法在这个框中写下。 - 1800 INFORMATION
显示剩余2条评论
0
将边权重乘以-1，在新图上找到最短路径。这将是原始图上的最长路径。
我猜这个问题的难度和原来的问题一样。 - 1800 INFORMATION
只需记住，您不能在带有负数的情况下使用Dijkstra算法。 - Joseph
0

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

sup i,j {inf i,j {n : n=从i到j的路径长度}}

你应该考虑使用像Flyod-Warshall这样的全节点最短路径算法，正如其他人所提到的那样。这将是O(V^3)的顺序。

如果你想要最长的可能路径，即

sup i,j {n : n=从i到j的路径长度}

你可以尝试使用Midhat的想法。（正如评论中指出的那样，这实际上与原问题一样复杂）我建议将权重反转为1/w，以保留正权重，假设原始权重是严格正的。

当处理负权重时，你可能还想查找Bellman和Ford算法。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接