algorithm - 高效的最大流量算法将尽可能多的人路由到一个位置？

Question

我正在尝试使用有向图确定一个有效的最大流量算法，其中给定n 个航班的列表（其中每个条目都有起始城市、结束城市、出发时间、到达时间和航班容量），将路由尽可能多的人从城市 A 开始并在城市 B 结束。我还希望能够返回一组可以乘坐的航班，以便尽可能多的人从城市 A 到达城市 B。我认为它可以只是 Ford-Fulkerson 算法或类似算法的实现，但我无法以有效的方式将此计划转换为最大流实例，特别是所述算法的伪代码看起来如何就像这样做之后。

标签： algorithmmax-flownetwork-flowford-fulkersonedmonds-karp

Answer 1

您正在考虑的算法可以解决问题，但是必须正确构建要处理的图表。

你的问题是时机。假设您想在 14:00 之前从A到C的人，我们总共有 4 个航班：

航班 1：A -> B，10:00 -> 11:00，Cap. 100
航班 2：A -> B，11:00 -> 12:00，船长。100
航班 3：B -> C，11:30 -> 12:30，Cap。100
航班 4：B -> C，12:30 -> 13:30，Cap。100

您可以在此处看到您可以填充所有航班并及时获得 200 个 from Ato C，但构建图表需要考虑时间。
我的建议是你没有一个节点来表示B，而是有几个节点：

(B, 11:00)- B11:00。
(B, 12:00)- B12:00。
(B, 12:30)- 当 3 号航班起飞时。
(B, 13:30)- 当 4 号航班起飞时。

从相关节点开始，任何可以离开的航班都B将添加到图表中一次。B

BB节点按照向前移动的时间顺序连接到具有无限容量的边中的其他节点。这允许乘客在不同时间之间“等待” B。

这个例子最终会得到以下边列表：

// 飞行边缘
[ (A, 10:00), (B, 11:00)], Cap. 100
[ (A, 11:00), (B, 12:00)], 章。100
[ (B, 11:30), (C, 12:00)], 章。100
[ (B, 12:30), (C, 13:00)], 章。100

// 等待边
[ (B, 11:00), (B, 11:30)], Cap. 无限
[ (B, 11:30), (B, 12:00)], 章。无限
[ (B, 12:00), (B, 12:30)], 章。无穷