图吞吐量算法

Question

我的任务是计算图表中的最大吞吐量。

描述图形的最简单方法是int[][]。内部数组是图中的节点，外部数组是连接图中每个节点的距离，例如：

new int[][] {
    {0, 5, 0, 0}, // node 0 (the "source")
    {0, 0, 4, 0}, // node 1
    {0, 0, 0, 8}, // node 2
    {0, 0, 0, 0}  // node 3 (the "destination")
}

因此，要从node 0（源）到node 3（目标），“最大吞吐量”将是每圈 4，因为：

• 5 个数据包可以从节点 0 到节点 1
• 4 个数据包可以从节点 1 到节点 2
• 8 个数据包可以从节点 2 到节点 3

在“每转”的基础上，瓶颈在node 1和之间node 2，其中最大吞吐量为 4。

可有人点我会解决这个“最大吞吐量”问题，以这种方式定义的任何给定的图形算法int[][]，并给出source和destination节点？

示例图将使用多个“源”和“目的地”进行扩展，我将需要在任何给定的“转弯”上计算整个系统的最大吞吐量。

我很感激以学习算法或“伪代码”的形式提供的帮助。

Answer 1

最大流量问题就是您正在寻找的：

\n\n

\n

在优化理论中，最大流量问题涉及找到通过单源、单汇流量网络的最大可行流量。

\n

\n\n

Edmonds\xe2\x80\x93Karp 算法是查找最大流的常用算法：

\n\n

\n

在计算机科学中，Edmonds\xe2\x80\x93Karp 算法是 Ford\xe2\x80\x93Fulkerson 方法的实现，用于在 O(VE ² ) 时间内计算流网络中的最大流。

\n

\n\n

从伪代码可以看出，它的实现并不是一个复杂的算法。这也是一个 C++实现。

\n\n

最小割可以与最大流问题结合起来，以便找到瓶颈（可能有多个）：

\n\n

\n

流网络中的切口，将源顶点和汇顶点分开，并使从切口的源侧指向切口的汇侧的边上的总权重最小化。如最大流最小割定理所示，该割的权重等于给定网络中可以从源发送到接收器的最大流量。

\n

\n\n

最小切割使用最大流量并查找第一个达到容量的边缘。

\n\n

了解更多内容，请参阅最大流量，最小切割。

\n