计算机技术与发展
計算機技術與髮展
계산궤기술여발전
COMPUTER TECHNOLOGY AND DEVELOPMENT
2014年
11期
54-56
,共3页
最大流%容量差%增广链%最短路径
最大流%容量差%增廣鏈%最短路徑
최대류%용량차%증엄련%최단로경
maximum flow%differential capacity%augmenting path%shortest path
网络最大流问题是图论中的经典问题之一，对于最大流问题有很多经典的算法，但这些经典算法皆有不足之处。针对其不足，文中通过引入容量差的概念，对算法进行了一些改进。改进算法的原则是优先选择路径最短且容量差最大的路径进行增广，若当路径长度一样并且容量差也一样时就要对其修正，然后选择修正后的路径，这样每次增广至少使一条弧达到饱和。通过实例说明了改进算法的可行性，整个运算过程可以在一个图上完成，直观性强并且方便计算，较传统算法更为有效。
網絡最大流問題是圖論中的經典問題之一，對于最大流問題有很多經典的算法，但這些經典算法皆有不足之處。針對其不足，文中通過引入容量差的概唸，對算法進行瞭一些改進。改進算法的原則是優先選擇路徑最短且容量差最大的路徑進行增廣，若噹路徑長度一樣併且容量差也一樣時就要對其脩正，然後選擇脩正後的路徑，這樣每次增廣至少使一條弧達到飽和。通過實例說明瞭改進算法的可行性，整箇運算過程可以在一箇圖上完成，直觀性彊併且方便計算，較傳統算法更為有效。
망락최대류문제시도론중적경전문제지일，대우최대류문제유흔다경전적산법，단저사경전산법개유불족지처。침대기불족，문중통과인입용량차적개념，대산법진행료일사개진。개진산법적원칙시우선선택로경최단차용량차최대적로경진행증엄，약당로경장도일양병차용량차야일양시취요대기수정，연후선택수정후적로경，저양매차증엄지소사일조호체도포화。통과실례설명료개진산법적가행성，정개운산과정가이재일개도상완성，직관성강병차방편계산，교전통산법경위유효。
The maximum network flow problem is one of the classical problems in graph theory,there are many classical algorithms for them,but all theories have shortcomings. For the shortcomings,the algorithm is improved by introducing the concept of differential capac-ity. The principle of improved algorithm is that the shortest path and maximum differential capacity is priority selection. When the length of path and differential capacity are the same,can choose the revised path,so that each augmentation can make an arc reach saturation at least. An practical example is given to demonstrate the feasibility,all of the procedure can be completed in one diagram,the intuition is strong and easy to calculate,the new algorithm is more effective than the traditional algorithm.
