迄今最快的网络流算法，网友：几乎与数学理论一样快

来源：互联网时间：2026-07-11 07:16:17

而且还是以最低成本计算最大运输流量的那种。

这波操作，来自苏黎世联邦理工学院计算机系的Rasmus Kyng团队（江湖人称“京爷”）。

其实早在两年前，京爷团队的“前代”成果就已经刷了一波存在感，还被Quanta Magazine评选为当年的计算机科学十大发现之一。

连网络流算法领域的先驱Daniel A. Spielman都忍不住点赞：

而就在最近，他们在ACM计算理论研讨会（STOC）上，又带来了一个“进化版”——

不管网络里是增加了还是删除了什么路径，都能以最低成本、最大传输流量的“姿势”，用几乎线性的速度把计算搞定。

这就好比徒步旅行，管你道路变复杂还是变陡峭，我照样保持高速前行，顺利抵达终点。

苏黎世联邦理工学院官方给出了一句很硬核的评价：

那么，京爷的团队到底是怎么做到的呢？

迄今最快的网络流算法

网络流，本质上是图论里的一种理论和方法，研究的是网络上的一类最优化问题。

这个问题最早可以追溯到1955年，当时T.E.哈里斯在研究铁路最大通量时，为了找出两点间的最大运输量而提出。

到了1956年，L.R.福特和D.R.富尔克森等人给出了解决这类问题的算法，网络流理论就此正式建立。

而且，网络流算法在解决现实问题的时候，价值相当可观。

比如你用欧洲运输网络，想找一条最快、最便宜的路线，把尽可能多的货物从哥本哈根运到米兰，这时候网络流算法就能派上用场了。

对于这类问题，以前计算最佳流量所需要的时间，甚至比处理网络数据本身还要长得多。

随着网络变得越来越庞大、越来越复杂，计算时间相对而言的增长速度，比问题本身的实际规模快得多。

这也正是为什么我们现在还会看到，有些计算机对网络中的流量根本算不过来。

但京爷团队提出的算法，一举打破了这种僵局——

不仅读取网络数据到得出解决方案所需的“额外”计算时间现在可以忽略不计，就算要重新设计路由（Route）或者添加新路由，也都基本没有额外开销。

原则上，所有计算方法都要面临一个挑战：必须多次迭代分析网络，才能找到最佳流量和最低成本路线。

在京爷团队之前，研究者们基本是在两种关键策略之间二选一：

一种方法是以铁路网络为模型，每次迭代都对整个网络进行计算，并修改交通流量。另一种方法则受电网中电力流的启发，每次迭代也计算整个网络，但对网络每个部分的修改流量，使用统计平均值。

京爷团队的做法则是——成年人当然不做选择题，两者的优势全都要，组合起来打造新方法：

最新的这项研究，提出了一系列针对增量图（incremental graphs）问题的几乎线性时间算法。

（增量图指的是随时间变化而动态变化的有向图，主要通过边的插入操作来改变结构。）

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

环检测（Cycle Detection）：检测图中是否存在环。强连通分量维护（Strongly Connected Component Maintenance, SCCs）：维护图中的强连通分量。单源最短路径（s-t Shortest Path）：计算图中单源到单目标的最短路径。最小成本流（Minimum-Cost Flow）：在满足容量限制的情况下，找到成本最小的流。