資源描述：
《求解最大流問題的matlab程序（matlab program for solving maximum flow problems）》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。
1、求解最大流問題的matlab程序（Matlabprogramforsolvingmaximumflowproblems）MaximumflowalgorithmAlgorithmidea:themaximumflowproblemisactuallyafeasibleflow{fij},whichmakestheV(f)reachthemaximum.IfyougiveafeasibleflowF,aslongasthereisnojudgmentinNaugmentingpathontheF,ifthereisanaugmen
2、tedpath,improvedF,anewfeasibleflowrateincreases;ifthereisnoaugmentingpath,getthemaximumflow.1.labelingmethodformaximumflow(Ford,Fulkerson)Startingwithafeasibleflow(ageneralzeroflow),thefollowinglabelingprocedureandtheadjustmentprocessarefolloweduntilnoaugmentingpatha
3、boutFcanbefound.(1)labelingprocessInthisprocess,thepointsinthenetworkaredividedintolabeledandunlabeledpoints,andthelabeledpointsaredividedintotwokinds:checkedandunchecked.Eachlabellabelinformationpointsareexpressedintwoparts:thefirstlabelshowthatthelabelfromwhichpoin
4、ttostartthetracebackpathfromtheVTtofindoutisaugmented;secondlabelissaidtohavecheckedwhetherthevertex.Atthestartofthelabel,markvs(s,0),whenvsisthelabel,butattheendofthecheckpoint,andtherestareunlabeledpoints,denotedas(0,0).TakealabelwithoutcheckingthepointVI,forallunl
5、abeledpoints,vj:A.forarc(VI,VJ),iffij0,thengivetheVJlabel(-vi,0),thentheVJpointbecomesthelabel,whichisnotchecked.Thus,VIbecomesalabeledandcheckedpoint,anditssecondlabe
6、lisdenotedas1.Repeatthestepsaboveand,onceVTismarked,indicateanextendedpathfromVItoP,andVTintotheadjustmentprocess.Ifallthelabelshavebeencheckedandthelabelprocessfails,thealgorithmendswiththefeasibleflowbeingthemaximumflow.(2)adjustmentprocessFromtheVTpoint,throughthe
7、firstlabelofeachpoint,backwardtracing,wecanfindtheaugmentingpathP.Forexample,ifthefirstlabelofVTisVK(or-vk),thenthearc(VK,VT)(orcorrespondingly(VT,VK))isthearcontheP.Next,checkthefirstlabelofVK,andifitisVI(or-vi),find(VI,VK)(orVI(VK)).CheckthefirstlabelofVI,andsoon,u
8、ntilvs.Atthispoint,theentireaugmentingpathisfound.CalculatetheQatthesametimeasyoulookfortheaugmentingpath:Q=min{min(cij-fij),minf*i
