2023年7月30日发(作者：)
最⼤流EK与Dinic算法最⼩费⽤最⼤流问题简述最⼤流问题是给⼀个有向⽹络，每条边都有⼀个容量，问从起点到终点最多能输出多少流。这是⼀个模型，在处理某些问题合适建模，就能利⽤这些现成的算法，使得问题得到解决。EK算法采⽤BFS找增⼴路，不断⽤流到这个点的最⼤流和现存容量的较⼩值进⾏更新，就这样每次找到⼀条更新整个图，然后添加反向弧，反向弧的容量与正向的和是等于整个容量，这个反向弧并不存在，只是为算法提供了修改的途径，有反悔的机会，添加反向边，更新残余量，直到没有路径可以到达。Dinic算法,在残量⽹络上操作（残量⽹络是包含反向弧的⽹络），BFS建层次图，DFS找路径，找到阻塞流就算成功，不⼀定是最⼤流，然后更新整个⽹络，重复整个过程，算法效率优于EK算法。最⼩费⽤最⼤流SPFA算法，利⽤费⽤建⽴⼀个⽹络，然后找费⽤和最少的⼀条路径（不考虑流量），然后在这条路径上找最⼩的容量边作为整条路的容量，计算价钱，然后当这条边的容量⽤了部分或全部之后添加反向弧（参数仍是费⽤，容量⽤完取消正向弧），继续重复上⼀个过程。
发布者：admin，转转请注明出处：http://www.yc00.com/xiaochengxu/1690723390a408118.html
评论列表（0条）