沿网络中的单个路径找到最大带宽

Question

我正在尝试搜索一种算法，该算法可以告诉我哪个节点的下载量最高（或上传）容量给定的有向图，其中权重对应于单个链接带宽。我看了看最大流量问题和Edmond-Karp算法。我的问题是：

1. 埃德蒙·卡普（Edmond-Karp）只是告诉我们，如果使用任何路径，我们可以从源到水槽获得多少吞吐量。正确的？
2. 埃德蒙·卡普（Edmond-Karp）没有告诉我们哪种路径可以为我们提供最大流量。正确的？

Answer 1

问题2的一种非常简单的方法是以下内容。按容量对边进行排序。以最低的容量去除边缘，并检查是否仍然有从$ S $到$ t $的路径。如果有的话，以第二低容量的速度移动边缘，依此类推。

在某个时候，通过删除容量$ c $的边缘，我们将从$ t $中脱离连接。现在，我们知道$ c $是从$ s $到$ t $的单个路径的最大容量。

该算法需要时间$ o（m^2）$，因为可以在时间$ o（m）$上进行连接检查，我们最多一次可以删除每个边缘。

现在，您可以通过在此还原图中找到任何$ S $ -T $路径来找到最大容量的实际路径（可能有很多）。

在考虑节点容量时，请记住更改图形以支持这一点。

Answer 2

给定路径，只是沿其迭代并找到最高容量的节点。

从评论中提取，让我们考虑这个更有趣的问题：

给定一个由链接$ e $连接的节点$ n $的网络，其中有限带宽$ b：e to mathbb {n} $，找到从$ s $到$ t $的路径，并带有最大bandwith。

换句话说，您正在寻找$ s $ - $ t $ - path $ p =（s，v_1， dots，v_k，t）$最大化

$ qquad displayStyle b（p）：= min {b（s，v_1），b（v_k，t） cup cup {b（v_i，v_i，v_i+1} mid I = 1 ， dots，k-1 } $

在所有$ s $ - $ t $ - paths中。

值得注意的是，周期不会改变路径bandwith $ b $，因此我们可以将自己限制在这方面的最小路径，这是$ b $ - 最佳的 跨树.

此外，请注意，在所有$ b $最佳的路径中，（至少）有一个具有subpath-ofimality属性，我们从最短的路径问题中知道，那就是最佳路径的所有部分路径都是最佳的（对于节点而言他们连接）。它不适合所有$ b $ - 最佳路径¹，但这不是问题：我们需要知道的是 是 A $ b $最佳路径可以通过$ b $最佳路径的串联构建。因此，我们可以局限于仅考虑（部分）路径。

因此，我们为贪婪的策略提供了足够的理由 Prim的算法: ：从$ s $开始，连续选择具有最大频带的边缘，在已经访问过的节点的那些边缘（未连接两个已经访问过的节点）的边缘。这只会发现$ b $ - 最佳路径，并与a $ b $ - 最佳的$ s $ - $ t $ - path（如果$ t $可从$ s $达到$ t $）。

这是在时间上运行$ O（| n |^2）$。

---

1. 考虑此图：

   
   ^[资源]

   所有$ s $ - $ t $ - paths都是最佳的，但是通过下节点的那些则具有非最佳的子路径。

Answer 3

这可以通过对Dijkstra进行简单修改来在O（vlogv + e）时间中完成

键（节点n）=单路径最大流量从s到n

更新密钥：如果P是N键（n）= min（键（P），Edge（p，n））的前身

这是因为所有路径p =（s，a_2，... a_m-1，a_m）

路径p = min中的最大流量（容量（a_m-1，a_m），p- {a_m}中的最大流量）

之所以起作用，是因为单路径最大流到x = max（路径中的最大流量所有路径p从s到x）