图形吞吐量算法

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")
}

要从节点0（源）到达节点3（目标），“每轮的最大吞吐量”将为4，因为：

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

按照“每轮”的基础计算，瓶颈在节点1和节点2之间，这里的最大吞吐容量为4。

有人能指导我使用一种算法来解决此类问题，对于给定的以int[][]方式定义的任何图形和给定的源和目标节点，都能计算出“最大吞吐量”吗？

示例图将扩展为具有多个“源”和“目标”的图，我需要在任何给定的“轮次”上计算整个系统的最大吞吐量。

我希望得到一些算法学习或“伪代码”的帮助。

- user7433212

---

我认为你所描述的通常被称为最大流。一旦知道了这个名字，很容易找到大量可搜索的信息。 - moreON

如果你正在寻找其中的一个瓶颈，你可以使用最小割算法（它使用最大流，并仅搜索容量已满的第一条边）。 - bigballer

一个通常用于最大流的好算法是Edmons-Karp。它的实现并不是特别困难。 - Gene

https://en.wikipedia.org/wiki/Maximum_flow_problem - Dmitry Bychenko

这是一个作业问题。典型的最大流类型问题。对于 OP 来说，输入类型甚至非常重要。建议关闭。 - Saeed Amiri

我投票关闭此问题，因为它是一道作业题，而且提问者没有展示出任何努力。 - Saeed Amiri

Answer 1

最大流问题是您正在寻找的内容:

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

Edmonds-Karp算法是查找最大流的常用算法：

在计算机科学中，Edmonds-Karp算法是Ford-Fulkerson方法的一种实现，用于计算具有O（VE²）时间复杂度的流网络中的最大流。

从伪代码中可以看出，它在实现时并不是一个复杂的算法。这里还有一个C ++ 实现。

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

在一个流网络中，切割将源和汇点从彼此分离，并最小化从切割的源侧指向切割的汇侧的边上的总权重。正如最大流最小割定理所示，这个切割的权重等于在给定网络中从源到汇可发送的最大流量。

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

在最大流，最小割中阅读更多内容。

- gsamaras