Ch9.3-4 Shortest-Path Algorithm, Network Flow Problem

《Ch9.3-4 Shortest-Path Algorithm, Network Flow Problem 》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、§3ShortestPathAlgorithmsGivenadigraphG=(V,E),andacostfunctionc(e)foreE(G).ThelengthofapathPfromsourcetodestinationis(alsocalledc(ei)weightedpathlength).eiP1.Single-SourceShortest-PathProblemGivenasinputaweightedgraph,G=(V,E),andadistinguishedvertex,s,findtheshortestweightedpathfromstoever

2、yothervertexinG.Negative-cost22cyclev1v2v1v2Note:Ifthereisno4131041–103negative-costcycle,2222v3v4v5v3v4v5theshortestpath84845656fromstosis11definedtobezero.v6v7v6v71/17§3ShortestPathAlgorithmsUnweightedShortestPathsSketchoftheidea1vv20:v31221:v1andv6Breadth-first0vvv33452:vandvsearch24

3、1v6v733:vandv57ImplementationTable[i].Dist::=distancefromstov/*initializedtobeexceptifors*/Table[i].Known::=1ifvischecked;or0ifnotiTable[i].Path::=fortrackingthepath/*initializedtobe0*/2/17§3ShortestPathAlgorithmsvoidUnweighted(TableT){intCurrDist;VertexV,W;for(CurrDist=0;CurrDist

4、ex;CurrDist++){for(eachvertexV)if(!T[V].Known&&T[V].Dist==CurrDist){T[V].Known=true;for(eachWadjacenttoV)IfVisunknownif(T[W].Dist==Infinity){yethasDist

5、end-forCurrDist*/}T=O(

6、V

7、2)Theworstcase:v9v8v7v6v5v4v3v2v13/17§3ShortestPathAlgorithmsImprovement12voidUnweighted(TableT)v1v2{/*TisinitializedwiththesourcevertexSgiven*/023QueueQ;v3v4v5VertexV,W;v6v7Q=CreateQueue(NumVertex);MakeEmpty(Q);13Enqueue(S,Q);/*Enqueuethesourcevertex*/while(!IsEmp

8、ty(Q)){V=Dequeue(Q);DistPathT[V].Known=true;/*notreallynecessary*/v11v03v7for(eachWadjacenttoV)v22v01v5if(T[W].Dist==Infinity){v300T[W].Dist=T[V].Dist+1;v4v42v01T[W].Path=V;vEnqueue(W,Q);v53v022}/*end-ifDist==Infinity*/v61v03v6}/*end-while*/v73v04v31DisposeQueue(Q);/*freememory*/}T=O(

9、

10、V

11、+

12、E

13、)4/17§3ShortestPathAlgorithmsDijkstra’sAlgorithm(forweightedshortestpaths)LetS={sandv’swhoseshortestpathshavebeenfound}iForanyuS,definedistance[u]=minimallengthofpath{s(viS)u}.Ifthepathsaregeneratedinnon-decreasingorder,thentheshortestp