图论问题，Java。哪种算法可以实现以下内容？

Question

我有一个图，其中包含X个节点和Y条边。这些边是加权的。问题在于从一个节点开始，到达另一个节点。现在问题来了；

想象一下这个问题。这些边就像道路，而边的权重是车辆在道路上行驶的最大重量限制。我们想要开一辆从A到B的最大卡车。因此，沿给定路径行驶的卡车的最大允许重量是该路径中所有边的最小重量。我想要从A到B的所有路径中具有最大的最大允许重量。

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

更新：我尝试了一些对我无效的方法。每个节点必须有每个入边的一个最大卡车。

- Algific

---

“从A到B。它将返回一个int，即该路线上最小的边缘。但与从A到B的其他路线相比，它是最大的边缘。” 什么？你说“从A到B最小，但从A到B最大”？ - Mirek Pluta

从A到B可能有多条路线。关键是我们想开最大的卡车从A到B。选择的边是所选路径中最小的边，但与其他从A到B的路径中最小的边相比是最大的。 - Algific

Answer 1

迪杰斯特拉算法应该可以使用，但在这种情况下，您的“距离”有些奇怪。您的“距离”是您可以到达节点的最大卡车大小。我们称其为节点v的M[v]。您需要按照从最大M[v]到最小M[v]（与正常的Dijkstra相反）的顺序处理节点，并计算从v到w的每个边缘e：

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

- Keith Randall

---

很好，现在每个节点的成本都初始化为整数最大值。这样做的默认成本是多少？ - Algific

所有节点默认为0，除了源节点以无限大开始。 - Keith Randall

好的，我现在会回到Eclipse。非常感谢你！ - Algific

脑海中浮现出一个想法，一个节点可以有多个入边。每条边都会“带”上一个最大边。这意味着如果到B有多种路径，这种方法将无法奏效？ - Algific

正确的，其中一个入边将获胜。假设没有平局，那么最后增加公式中的M[w]的那个入边将获胜。可以反向重建结果路径。从w=目标开始，对于每个w，检查所有的边e:v->w，并取min(e.weight, M[v]) == M[w]的v。 - Keith Randall

Answer 2

这几乎与最大流问题完全相同，可以使用Ford-Fulkerson算法有效地解决。

正如Keith在评论中指出的那样，必须稍微改变算法以仅查找最大化最小路径段的一条路径，因为卡车不能分成多个部分。

- Konrad Rudolph

---

最大流不太正确，这将允许您将卡车分成几块并将每个部分发送到不同的路线。 - Keith Randall

@Keith：没错，不完全像最大流。不过我喜欢把卡车切碎的想法。;-) - Konrad Rudolph

Answer 3

我想你正在寻找这个

最短路径

编辑：实际上你不是，最大流链接是正确的

- dagoof

Answer 4

如果我理解正确的话，你是在问：“从A到B最大的卡车是多大？”

要应用Dijkstra算法，您需要一种对“成本”进行建模的方法。如果想使用标准实现，则可以将权重的倒数分配给成本。因此，最高成本的边缘是具有最小最大权重的边缘。当然，由于您可能想使用漂亮的整数，因此您可以简单地修改比较而不是实际使用倒数。

- McPherrinM

Answer 5

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

- Edmund

Answer 6

你可以采用一种最小生成树的方法。从高流量边开始，每次连接一个节点，直到A和B相连。你添加到图中的最后一条边就是你必须穿越的最低流量边，才能从A到达B。这可能不是最有效率的解决方案（最坏情况下O(N²)），但至少它很简单明了。

- Corey Porter

Answer 7

这既不是最短路径问题，也不是最大流问题。实际上并不存在问题。他说 - 想要从 A 到 B 的所有路径的最大权重。因此通过 BFS 生成所有从 A 开始的路径。对于所有以 B 结尾的路径，找到路径边缘的最小权重。

- zufar

---

你在进行BFS时，实际上会如何存储路径片段？ - Algific

那么这意味着图不是小的，路径数量可能很大？我猜你对从A到B的单条路径感兴趣，且最大权重已被允许？做法如下：通过任何算法（例如Dijkstra）找到A-B路径。然后删除最小权重的边。再次查找A-B路径。重复此过程，直到没有A-B路径为止。在删除边之前存在的最后一条路径将是具有最大权重的路径。 - zufar

Answer 8

使用迪杰斯特拉算法，将最大卡车重量的倒数作为边的成本，并将各个边的最大权重作为总路线成本。

即edge_cost等于1/(允许的最大卡车重量)， 给定路线的total_cost是该路线中所有边的个体edge_cost的最大值。

- jilles de wit

Answer 9

上面的各种答案都提出了使用修改后的权重函数的Dijkstra算法。例如，w(e) = -c(e)或'w(e) = 1/c(e)'，其中w(e)是算法使用的边的权重，c(e)是原始问题公式中边的容量。

这些方法不起作用。

很容易就能找到反例证明这会产生错误的结果。例如，考虑以下图形：

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

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

修改算法的松弛步骤是可行的，即使用函数min和大于号（>）代替加法（+）和小于号（<），并使用最大堆而不是最小堆。如果我们取反边权重并使用小于号，则可以避免最后两个修改，但我们无法避免替换+，因为我们需要某个运算符@，其中对于所有a值，a @ a = a，而+仅适用于a=0。

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

一个好的练习是正式证明修改后的算法是正确的。需要证明的是： - 如果u是任何循环迭代中具有最大值d(u)的节点，则涉及未标记节点的路径不能创建到u的路径，使得距离大于d(u)。

直观来看很容易理解，因为所有其他未标记的节点距离小于（或等于）“u”的距离（因为我们选择u作为具有最大距离的节点），而生成路径的距离是通过连续调用min产生的，因此它只能变小，而不能变大。

- Dimitris Andreou