苏黎世联邦理工学院研发史上最快网络流算法

近日， 苏黎世联邦理工学院计算机系的 Rasmus Kyng 在网络流算法方面取得了显著的进展。其团队开发了一种新的网络流算法，能够在几乎线性的时间里计算最大运输流量，这意味着其运行时间将接近数学理论中的计算速度。

Kyng 的博士生导师、耶鲁大学应用数学和计算机科学教授丹尼尔·A·斯皮尔曼（Daniel A. Spielman）将这种”快得离谱“的算法比作保时捷超跑；苏黎世联邦理工学院官方也做出评价：超快算法为未来高效计算超大型动态变化的网络奠定了基础，有望改变整个研究领域。

那么，是什么让 Kyng 的计算方法能比其他网络流算法都要快呢？

原则上，所有计算方法都必须多次迭代分析网络，以找到最佳流量和最低成本路线。在 Kyng 团队之前，研究人员一般通过两种方案来解决这一问题：

• 以铁路网络为模型，在每次迭代中对整个网络进行计算，并对交通流量进行修改；

• 在每次迭代中计算整个网络，但对网络每个部分的修改流量使用统计平均值。

而 Kyng 的团队则是将这两种策略各自的优势结合在一起，创造出了一种新的组合方法。Kyng 团队成员表示，“我们的方法是基于很多小的、低成本的计算步骤，这些步骤加起来比几个大的步骤快得多。”

论文中提出的算法主要解决以下几个问题：

• 环检测（Cycle Detection）：检测图中是否存在环。

• 强连通分量维护（Strongly Connected Component Maintenance, SCCs）：维护图中的强连通分量。

• 单源最短路径（s-t Shortest Path）：计算图中单源到单目标的最短路径。

• 最小成本流（Minimum-Cost Flow）：在满足容量限制的情况下，找到成本最小的流。

相比于现有算法，Kyng 团队新网络流算法具有独特优势：

• 基于断链的标号算法：新算法广泛吸取了标号算法的最新成果，并引进了断链的基本概念，提出了一种基于断链求解网络最大流的新标号算法。这种方法在处理大规模、高复杂度的网络流问题时表现更为优异，能够有效提高算法的效率和准确性。

• 仿真实验验证：通过实例和仿真实验进行了验证，证明了新算法的有效性和可靠性。

网络流算法在多个领域都发挥着重要作用。它通过构建网络模型来优化各种流程，提高效率，降低成本。在物流优化方面，算法帮助优化运输路径，提升运输效率并减少开支。电路布线设计方面，也通过此算法，确保电路运行的高效性和可靠性。此外，在网络设计中，算法可以优化数据传输路径，保障数据传输的高效与稳定。

该研究不仅为为解决以前无法有效计算的非常大规模问题奠定了基础，同时，还改变了计算机计算复杂任务的方式。

参考链接：

https://ethz.ch/en/news-and-events/eth-news/news/2024/06/researchers-at-eth-zurich-develop-the-fastest-possible-flow-algorithm.html

论文原文：

https://dl.acm.org/doi/10.1145/3618260.3649767