廊坊师范学院学报（自然科学版）
廊坊師範學院學報（自然科學版）
랑방사범학원학보（자연과학판）
JOURNAL OF LANGFANG TEACHERS COLLEGE
2009年
6期
22-24
,共3页
分层%增量网络%最大容量有向路算法%有向路%复杂度
分層%增量網絡%最大容量有嚮路算法%有嚮路%複雜度
분층%증량망락%최대용량유향로산법%유향로%복잡도
针对单源、单汇网络给出最大流问题的一个新算法--最大容量有向路算法,算法的核心思想是利用分层原理在增量网络中反复寻找从源点到汇点的在一定规则下的容量最大的有向路,直至找不到有向路为止.给出算法的复杂度为O(mn)与最大流问题的两个具有代表性的算法--Ford-Fulkerson算法和Dinic算法,作了复杂性和实例比较,结论是最大容量有向路算法的效果好于Ford-Fulkerson,算法不低于Dinic算法.该算法完全能够编程实现,仿真试验结果表明,算法效果良好.
針對單源、單彙網絡給齣最大流問題的一箇新算法--最大容量有嚮路算法,算法的覈心思想是利用分層原理在增量網絡中反複尋找從源點到彙點的在一定規則下的容量最大的有嚮路,直至找不到有嚮路為止.給齣算法的複雜度為O(mn)與最大流問題的兩箇具有代錶性的算法--Ford-Fulkerson算法和Dinic算法,作瞭複雜性和實例比較,結論是最大容量有嚮路算法的效果好于Ford-Fulkerson,算法不低于Dinic算法.該算法完全能夠編程實現,倣真試驗結果錶明,算法效果良好.
침대단원、단회망락급출최대류문제적일개신산법--최대용량유향로산법,산법적핵심사상시이용분층원리재증량망락중반복심조종원점도회점적재일정규칙하적용량최대적유향로,직지조불도유향로위지.급출산법적복잡도위O(mn)여최대류문제적량개구유대표성적산법--Ford-Fulkerson산법화Dinic산법,작료복잡성화실례비교,결론시최대용량유향로산법적효과호우Ford-Fulkerson,산법불저우Dinic산법.해산법완전능구편정실현,방진시험결과표명,산법효과량호.
