小编Yun*_*Lee的帖子

我在想一个算法来解决下面的问题:

由顶点和边组成的给定图.

有N个客户想要从顶点行进到另一个顶点.每个客户需求都需要一个有向边来连接两个顶点.

问题是如何找到满足所有客户要求的最小边数？

有一个简单的例子:

• 客户1想要从顶点a行进到顶点b.
• 客户2想要从顶点b行进到顶点c.
• 客户3想要从顶点a行进到顶点c.

最简单的方法是为每个客户提供优势:

• 边1:顶点a - >顶点b
• 边2:顶点b - >顶点c
• 边3:顶点a - >顶点c

但实际上只需要2个边缘(即边缘1和边缘2)来满足三个客户的要求.

如果客户数量很大,如何找到满足所有客户要求的最小边缘？

有没有算法来解决这个问题？