图论问题，Java。哪种算法实现如下

StackOverflow https://stackoverflow.com/questions/1805619

  •  05-07-2019
  •  | 
  •  

题

我有一个图表，有X个节点和Y个边缘。加权边缘。重点是从一个节点开始，然后在另一个节点停止。现在问题来了;

可视化问题。边缘是道路，边缘重量是在道路上行驶的车辆的最大重量限制。我们希望驾驶最大的卡车从A到B.因此，采用给定路径的卡车的最大允许重量是该路径中所有边缘的最小重量。我希望从A到B的所有路径的最大允许重量最大。

我可以使用某种Dijkstra算法来解决这个问题吗？我不确定如何以我可以实现的算法的形式表达这个问题。任何帮助深表感谢。

<强>更新 我测试了一些对我不起作用的东西。每个进入边缘的节点必须有一个最大卡车。

有帮助吗？

解决方案

Dijkstra的算法应该有效，但你的<！>“距离<！>”;在这种情况下有点奇怪。你的<！> quot;距离<！>是您可以到达节点的最大尺寸卡车。让我们称之为节点v的M [v]。你需要按照从最大M [v]到最小M [v]（与普通Dijkstra相反）的顺序处理节点，并计算从v到w的每个边e： / p> 

M[w] = max(M[w], min(e.weight, M[v]))

其他提示

这听起来（几乎）完全像最大流量问题，可以使用有效解决 Ford-Fulkerson算法。

正如Keith在评论中指出的那样，最大算法必须略有变化才能找到一条路径，并且最小路径段最大化，因为卡车可以<！>＃8217; t分成多个部分。

我认为你正在寻找这个

最短路径

编辑：实际上你没有，并且最大流量链接是正确的

所以如果我理解正确的话，你会问<！>“什么是最大的卡车可以从A开到B <！>

要应用Dijkstra算法，您需要一种方法来模拟<！> quot; cost <！> quot;。如果要使用标准实现，可以将权重的倒数分配给成本。因此，最高成本边缘是具有最低最大重量的边缘。当然，既然你可能想要使用漂亮的整数，你可以简单地修改比较而不是实际使用反转。

您正在寻求优化[ http://en.wikipedia.org/wiki/Flow_network ] 。容量是道路的最大重量限制;而流量就是卡车的重量。

您可以采用某种最小生成树方法。一次一个边连接节点，首先连接最高流边，直到A和B连接。您添加到图表中的最后一个边缘是您必须交叉从A到B的最低流量边缘。可能不是最有效的解决方案（O（N 2 ）最差情况） ，但至少它是直截了当的。

这既不是最短路径问题，也不是最大流量问题。实际上没有问题。他说 - 要求所有路径A到B的最大权重。所以从BFS生成A的所有路径。对于以B结尾的所有路径，找到路径边缘的最小权重。

使用 Dijkstra算法，以最大卡车重量的倒数作为边际成本，以及单个边缘权重的最大值作为总路由成本。

即。 edge_cost等于1 /（允许的最大卡车重量） 给定路线的total_cost是路线中所有边缘的单个<=>的最大值。

上面的各种答案简单地提出了具有修正权重函数的Dijkstra算法。例如，w(e) = -c(e)或'w（e）= 1 / c（e）'，其中w(e)是算法使用的边的权重，c(e)是边的容量。原始问题的表述。

这些不起作用。

人们可以很容易地创建反例，这会产生不正确的结果。例如，考虑图表：

a---3-->b---3--->c---3-->d
 \                       ^
  \                      |
   \----------3----------|

假设a（'算法公式中节点d的距离）的值为零。从(-3)+(-3)+(-3) = -9到-3的两条路径在此问题中是等效的。然而，如果我们只是否定边缘容量，使用长路径的距离（d）(1/3)+(1/3)+(1/3)=1，而使用短路径则(1/3)。如果我们反转边缘容量，使用长路径的距离（d）将是+，而使用短路径的距离（d）将是<。

将工作的是修改算法的松弛步骤，即不使用加法（min）和小于（>）的函数，分别使用函数<= >和大于（@），并使用最大堆而不是最小堆。如果我们否定边权重并使用less-than，我们可以避免最后两次修改，但是我们无法避免替换a @ a = a，因为我们需要一些运算符a=0 where u所有d(u)值，而<=>仅适用于<=>。

所以，我看到的唯一正确答案是Keith Randall给出的第一个答案。

一个很好的练习是正式证明修改后的算法是正确的。需要证明的是： - 如果<=>是在任何循环迭代中具有最大值<=>的节点，则没有涉及未标记节点的路径可以创建<=>产生大于<=>的距离的路径。

直观地，很容易看到，因为所有其他未标记的节点的距离小于（或等于）'u'的距离（因为我们选择<=>作为具有最大距离的距离），并且距离是生成的路径是由<=>的连续调用产生的，因此它只能变小，而不是变大。

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top