我在前几年的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英里"。这是两个相距最远的村庄之间的道路长度。
那么我应该按照我描述的方式来做吗？或者有一种更简单、计算成本更低的方法吗？
看起来您可以使用以下任一项：
- Floyd-Warshall算法
- Johnson算法
不过，我不能给你太多关于它们的指导——我不是专家。
因此，Dijkstra的一个实现运行O（VlogV+E），使您的方法的复杂性大约为V^2logV+VE。请参阅DADS。但也许更直观的是运行所有成对的最短路径算法中的一个，比如Floyd-Warshall或Johnsons。不幸的是，对于稠密图（接近于E=V^2的完全图），它们都大致为O（V^3）。
这是北方道路的问题吗？
您可以使用Dijkstra的实现，如下所示：
- 选取一个随机节点（a），从节点a运行Dijkstra，找到离它最远的节点。将该节点标记为节点b
- 从节点b开始再次运行Dijkstra，找到离它最远的节点。将该节点标记为节点c
我没有证据证明这一点，但我认为b和c将是最远的节点。您可能需要再运行一次迭代（我仍在考虑）。
将边权重乘以-1，找到新图上的最短路径。这将是原始图上最长的路径
如果您想要的最长最短路径
supi，j｛inf i，j｝n:n＝i和j之间的路径的长度｝｝
你当然应该考虑像其他人提到的Flyod Warshall这样的全节点最短路径算法。这将是O（V^3）的顺序。
如果你想要最长的路径，那就是
supi，j｛n:n＝i和j之间的路径的长度｝
你可以试试米哈特的主意。（这确实和评论中指出的原始问题一样复杂）不过，我建议将权重反转为1/w，以保留正权重，因为原始权重是严格正的。
在处理负权重时，您可能需要查找的另一种算法是Bellman和Ford 的算法