0

我了解残差图是什么。但是水平图是什么意思呢? http://en.wikipedia.org/wiki/Dinic%27s_algorithm

4

2 回答 2

1

来自维基百科的文章,级别图是带有边的残差图的子图

E_L = {(u, v) in E_f : dist(v) = dist(u) + 1},

其中E_f是残差图中的边集,是从源到dist(w)的未加权距离。sw

在英语中,E_L由残差图的边缘组成,这些边缘属于来自 的一些未加权最短路径s

于 2015-03-04T14:33:47.820 回答
0

水平图中,两个顶点之间的边具有相同的距离标签不被保留。在网络流中,我们使用 BFS 来查找级别图。

我们还删除了 sink 不可到达的顶点以及 source 不可到达的顶点。

于 2017-11-01T17:17:35.450 回答