计算机应用
計算機應用
계산궤응용
COMPUTER APPLICATION
2014年
4期
969-972
,共4页
最大动态流%时间重复流%关键弧%最小费用增广路%最小动态截
最大動態流%時間重複流%關鍵弧%最小費用增廣路%最小動態截
최대동태류%시간중복류%관건호%최소비용증엄로%최소동태절
maximum dynamic flow%temporally repeated flow%vital arc%minimum cost augmenting path%minimum dynamic cut
针对时间容量网络的最大动态流的关键弧问题,首先分析了经典的Ford-Fulkerson最大动态流算法,在此基础上简化了最大动态流算法,并由此提出一个基于最小费用增广路来寻找最大动态流关键弧的改进算法.算法将计算新网络最大动态流时共有的最小费用路保留,去掉了自然算法中重复的计算.与自然算法进行对比分析,结果表明改进算法比自然算法的效率更高.
針對時間容量網絡的最大動態流的關鍵弧問題,首先分析瞭經典的Ford-Fulkerson最大動態流算法,在此基礎上簡化瞭最大動態流算法,併由此提齣一箇基于最小費用增廣路來尋找最大動態流關鍵弧的改進算法.算法將計算新網絡最大動態流時共有的最小費用路保留,去掉瞭自然算法中重複的計算.與自然算法進行對比分析,結果錶明改進算法比自然算法的效率更高.
침대시간용량망락적최대동태류적관건호문제,수선분석료경전적Ford-Fulkerson최대동태류산법,재차기출상간화료최대동태류산법,병유차제출일개기우최소비용증엄로래심조최대동태류관건호적개진산법.산법장계산신망락최대동태류시공유적최소비용로보류,거도료자연산법중중복적계산.여자연산법진행대비분석,결과표명개진산법비자연산법적효솔경고.