想象一个具有多个接收器和多个源的双向网状网络图。
在此示例中，假设节点 6 和 20 是源，节点 4、11、12 和 21 是接收器。 现在想象某种流体通过这个网络从源头流向汇点。
是否有一种算法可以找到两个节点之间任何给定链路的流向？
最佳答案
这个问题可以描述为multi-commodity flow problem ，就像 @Luka 提到的。
在多商品流动问题中，一种或多种商品需要从网络中的源分配到汇。与许多其他图算法不同，允许多个接收器和源。多商品流动问题可以使用线性优化来解决。古罗比有一个great example script implemented in Python .
如果您需要它在图表中使用双向边，只需在初始化边、容量和成本时包含两个方向即可。否则，这个示例非常适合问题中的用例。
对于没有/无法获得 Gurobi 许可证的人(学术免费一年)，请查看此 repo相反。
关于查找网络中流向的算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/73136785/