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 英里”。这是两个相距最远的村庄之间的道路长度。

那么我应该按照我描述的方式去做，还是有一种更简单、计算成本更低的方法？

4

6 回答 6

3

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

不过，我不能给你太多关于它们的指导——我不是专家。

于 2008-10-04T06:05:53.813 回答
2

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

于 2008-10-04T06:10:03.197 回答
1

这是北方道路的问题吗？

于 2008-10-04T08:33:00.133 回答
0

您可以按如下方式使用 Dijkstra 的实现：

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

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

于 2008-10-04T06:03:32.947 回答
0

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

于 2008-10-04T06:14:15.733 回答
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 的算法

于 2008-10-04T08:30:34.990 回答