CAJ | 학술논문

给出一种求解网络最大流的新算法，该算法是针对增广链选取的顺序不当而无法得到理想的最大流，且在计算过程中每步都需要画一个网络图等问题进行的改进。利用分层及度差的概念，在选择增广链时优先选择路径最短且度差较大的路径，相同层次度差相同时优先选择容差较大的路径，在饱和的弧上画上终止符。最后用实例进行了验证并和Ford-Fulkerson算法做了比较，体现了它的高效性，避免了标号，且只需要在一个图上即可完成。整个运算过程直观性强，计算方便。
급출일충구해망락최대류적신산법，해산법시침대증엄련선취적순서불당이무법득도이상적최대류，차재계산과정중매보도수요화일개망락도등문제진행적개진。이용분층급도차적개념，재선택증엄련시우선선택로경최단차도차교대적로경，상동층차도차상동시우선선택용차교대적로경，재포화적호상화상종지부。최후용실례진행료험증병화Ford-Fulkerson산법주료비교，체현료타적고효성，피면료표호，차지수요재일개도상즉가완성。정개운산과정직관성강，계산방편。
It provided a new algorithm for solving maximum network flow. Due to the improper selection order of augmented chain could not obtain the ideal maximum flow and each step in the process of calculation needs to draw a network diagram,the algorithm does some improvement. The new algorithm makes use of layered network and the concept of degree of difference,gives priority to the shortest path and greater degree of difference when choosing augmenting path. It gives priority to the greater allowance path when degrees of difference are same under the same layer. And draws terminators on the arcs have reached saturation. Finally the algorithm is proved through the ex-ample and makes comparison with Ford-Fulkerson algorithm,showing its efficiency,and avoiding the labeling process,the entire process only needs drawing a diagram to be completed. It is strongly intuitive and convenient to calculate.