问题标签 [edmonds-karp]
For questions regarding programming in ECMAScript (JavaScript/JS) and its various dialects/implementations (excluding ActionScript). Note JavaScript is NOT the same as Java! Please include all relevant tags on your question; e.g., [node.js], [jquery], [json], [reactjs], [angular], [ember.js], [vue.js], [typescript], [svelte], etc.
algorithm - 高效的最大流量算法将尽可能多的人路由到一个位置？
我正在尝试使用有向图确定一个有效的最大流量算法，其中给定n 个航班的列表（其中每个条目都有起始城市、结束城市、出发时间、到达时间和航班容量），将路由尽可能多的人从城市 A 开始并在城市 B 结束。我还希望能够返回一组可以乘坐的航班，以便尽可能多的人从城市 A 到达城市 B。我认为它可以只是 Ford-Fulkerson 算法或类似算法的实现，但我无法以有效的方式将此计划转换为最大流实例，特别是所述算法的伪代码看起来如何就像这样做之后。
algorithm - 如何将 Edmonds & Karp 算法用于残差图
我正在解决 Edmonds 和 Karp 算法。在普通网络上，我知道如何使用它，实际上我不确定/我不知道如何在残差图上使用算法，因此存在后边。
谁能告诉我，那里的迭代是如何完成的？
python - Edmonds–Karp 时间复杂度
我正在尝试为无向图实现 Edmonds–Karp 算法的一个版本。下面的代码有效，但在处理大矩阵时非常慢。
是否可以让 Edmonds–Karp 算法运行得更快，或者我应该继续使用另一种算法，例如“Push Relabel”？我虽然有某种与 bfs 合作的出队，但我不知道该怎么做。
编码：
jgrapht - 如何使用 EdmondsKarp 最大流算法的自定义边缘实现
我正在尝试实现和模拟一个可以尝试一些路由方法的网络。
我的问题是我的一种路由方法是要求我计算 MaxFlow/MinCut。
我有一个边缘的自定义实现，我在其中添加了一些新字段，例如容量。这是我的实现：
当我尝试使用 EdmondsKarpMFImpl 时，我的问题是该算法使用边缘权重作为容量。
问题：如何使用我的边缘实现？
问题：如何获得 MinCut/MaxFlow 中的所有边？
谢谢！
jgrapht - 如何用 Edmonds Karp Impl 定义割集？
我正在使用 JGraphT，并且正在使用 EdmondsKarpMFImpl。
问题是：如何定义整个边集什么是最小切割中的“参与”。
我尝试使用该 getCutEdges方法，但它只返回 1 条边。
我有以下图表：
（所有边都有一个权重值（1）和一个剩余容量值（10））
使用这种方法，我只能在 Source 节点 (1) 和 Sink 节点 (5) 之间获得前 2 条边 (1-2 & 1-7)
我想检索最小切割中的所有边缘。例如，在上面的情况下，它应该返回：1-2、1-7、2-3、7-8、3-4、8-5、4-5（关于边缘的顺序我不关心）
图表如下所示：
polynomials - 问题 X 和分区问题之间的 Karp 约简以显示 NP 完全性
我应该通过 Karp 将其简化为分区问题来证明以下问题是 NP 完全的。问题 X 是根据以下因素在不同年龄组之间分配疫苗剂量：
给定：D 个疫苗剂量，n 个年龄组，a 1到 a n作为输入，其中年龄组 k 由 a k个个体组成，d 1到 d n作为输入，并且年龄组 k 中的每个个体接受 d k剂，至少 t每个年龄组的k % 必须完全接种疫苗，剩余剂量的最大数量可以是 S。
我应该证明这个问题是NP完全的。其中一个步骤是在此问题和分区问题之间进行 Karp 约简。我试图以各种方式减少这种情况，但没有成功。有任何想法吗？伪代码将是理想的。
graph-algorithm - 为什么流量网络中的圆圈意味着有多个合法的流量功能？
我试图理解为什么如果我在残差网络上运行 DFS 并发现有一个有向圆，这意味着在同一个网络上有多个可能的合法流函数具有相同的最大值。
谢谢你