Paths in graphs - People

1 Rstsearch readilyidenti esalltheverticesofa ndsexplicitpathstothesevertices, summarizedinitssearch tree( ).However, thesepathsmightnotbethemosteconomicalone spossi-ble. Inthe gure, vertexCis reachablefromSbytraversingjustoneedge, whiletheDFStreeshowsa pathof length3. Thischapteris aboutalgorithmsfor differentverticesofa graphareseparatedfromeach other:Thedistancebetweentwonodesis thelengthof geta concretefeelforthisnotion,considera physicalrealizationof a graphthathasa ballforeach vertexanda pieceof stringforeach edge. If youlifttheballforvertexshighenough,theot herballsthatgetpulledupalongwithit ndtheirdistancesfroms, (a)A simplegraphand(b)itsdepth- rstsearch tree.(a)EASBDC(b) physicalmodelof a , vertexBisatdistance2fromS, , thestringsalongeach ,edge(D;E) ,theliftingofspartitionsthegraphintolaye rs:sitself, thenodesatdistance1fromit,thenodesatdist ance2fromit, convenientway tocomputedistancesfromstotheothervertice sis toproceedlayerbylayer.

2 Oncewehavepickedoutthenodesatdistance0;1 ;2;::: ;d, theonesatd+ 1areeasilydetermined:theyarepreciselythe as-yet-unseennodesthatareadjacenttothela yeratdistanced. Thissuggestsaniterativealgorithminwhich twolayersareactiveatanygiventime:somelay erd, which hasbeenfullyidenti ed,andd+ 1, which is beingdiscoveredbyscanningtheneighborsof rstsearch (BFS)directlyimplementsthissimplereasoni ng( ).Ini-tiallythequeueQconsistsonlyofs, theonenodeatdistance0. Andforeach subsequentdistanced= 1;2;3;:::, thereis a pointintimeatwhichQcontainsallthenodesat distancedandnothingelse. Asthesenodesareprocessed(ejectedoffthefr ontofthequeue),theiras-yet-unseenneighbo rsareinjectedintotheendof 's tryoutthisalgorithmonourearlierexample( )tocon rmthatit doestherightthing. IfSis thestartingpointandthenodesareorderedalp habetically, rstsearch tree, ontheright,containstheedgesthroughwhich each nodeis earlier, ithasthepropertythatallitspathsfromSaret heshortestpossible.

3 It is ciencyWe havedevelopedthebasicintuitionbehindbrea dth- thatthealgorithmworkscorrectly, weneedtomakesurethatit ,precisely, is thatForeachd= 0;1;2;:::, thereisa momentatwhich (1)allnodesatdistance dS. Dasgupta, , (G;s)Input:GraphG= (V;E), directedor undirected;vertexs2 VOutput:Forall verticesureachablefroms, dist(u) is setto the allu2V:dist(u) =1dist(s) = 0Q= [s](queuecontainingjusts)whileQis notempty:u=eject(Q)for all edges(u;v)2E:if dist(v) =1:inject(Q;v)dist(v) =dist(u) + 1fromshavetheirdistancescorrectlyset;(2) allothernodeshavetheirdistancessetto1; and(3) havealreadydiscussedboththebasecaseandth einductivestep. Canyou llinthedetails?Theoverallrunningtimeofth isalgorithmislinear,O(jVj+jEj), forexactlythesamereasonsasdepth- vertexis putonthequeueexactlyonce, whenit is rsten-countered,sothereare2jVjqueueopera tions. Therestof theworkis doneinthealgorithm'sinnermostloop.

4 Overthecourseofexecution,thislooplooksat each edgeonce(indirectedgraphs)ortwice(inundi rectedgraphs),andthereforetakesO(jEj) :howdotheirexplorationstylescompare?Dept h- rstsearch makesdeepincursionsintoa graph ,retreatingonlywhenit runsoutof thewonderful,subtle, andextremelyusefulpropertieswesaw alsomeansthatDFScanenduptakinga longandconvolutedroutetoa vertexthatis actuallyverycloseby, rstsearch , shallowersearch,ratherlikethepropagation of a waveuponwater. Andit is achievedusingalmostexactlythesamecodeasD FS butwitha queueinplaceof a :sinceweareonlyinterestedindistancesfrom s, wedonotrestartthesearch inotherconnectedcomponents. breadth- rstsearch onthegraphof visitationafterprocessingnode[S]S[A C D E]A[C D E B]C[D E B]D[E B]E[B]B[ ] rstsearch , supposeyouaredrivingfromSanFranciscotoLa sVegas, andwantto ndthequickestroute. Pickingtherightcombinationof themis a shortest-pathprobleminwhich thelengthofeach edge(each stretch ofhighway)is , wewilldealwiththismoregeneralscenario, annotatingeveryedgee2 Ewitha lengthle.

5 Ife= (u;v), wewillsometimesalsowritel(u;v) 's donothavetocorrespondtophysicallengths. Theycoulddenotetime(drivingtimebetweenci ties)ormoney(costof takinga bus),oranyotherquantitythatwewouldliketo conserve. Infact,therearecasesinwhich weneedtousenegativelengths, butwewillbrie Dasgupta, , 's rstsearchBreadth- rstsearch toa moregeneralgraphG= (V;E)whoseedgelengthslearepositiveintege rs?A moreconvenientgraphHereis a simpletrick forconvertingGintosomethingBFScanhandle: breakG's longedgesintounit-lengthpieces, byintroducing dummy nodes. constructthenewgraphG0,Foranyedgee= (u;v)ofE, replaceit byleedgesoflength1, byaddingle , andthedistancesbetweenthemareexactlythes ameasinG. Mostimportantly, , ef ciencywerenotanissue, wecouldstophere. ButwhenGhasverylongedges, theG0it engendersisthicklypopulatedwithdummynode s, andtheBFSspendsmostofitstimediligentlyco mputingdistancestothesenodesthatwedon' seethismoreconcretely, ,andimaginethattheBFS, startedatnodesofG0, advancesbyoneunitofdistanceperminute.

6 Forthe rst99minutesit tediouslyprogressesalongS AandS B, anendlessdesertof wecansnoozethroughtheseboringphasesandha veanalarmwakeusupwheneversomethingintere stingis happening speci cally, wheneveroneof therealnodes(fromtheoriginalgraphG) is reached?We dothisbysettingtwoalarmsattheoutset,onef ornodeA, settogooffattimeT= 100,andoneforB, attimeT= 200. Theseareestimatedtimesofarrival, dozeoffandawakeatT= 100to ,theestimatedtimeof arrivalforBis adjustedtoT= , atanygivenmomentthebreadth- rstsearch is advancingalongcertainedgesofG, andthereis analarmforeveryendpointnodetowardwhich it ismoving, settogooffattheestimatedtimeof arrivalatthatnode. Someof thesemightbeoverestimatesbe-causeBFSmay later ndshortcuts, asa resultof futurearrivalselsewhere. Intheprecedingexample, a quickerroutetoBwasrevealeduponarrivalatA . However,nothinginterestingcanpossibly happenbeforeanalarmgoesoff.

7 Thesoundingofthenextalarmmustthereforesi gnalthearrivalof thewavefronttoa realnodeu2 VbyBFS. Atthatpoint,BFSmightalsostartadvancingal ongsomenewedgesoutofu, alarmclock algorithm faithfullysimulatestheexecutionof BFSonG0. Setanalarmclock fornodesattime0. Repeatuntiltherearenomorealarms:Say thenextalarmgoesoffattimeT, fornodeu. Then: ThedistancefromstouisT. Foreach neighborvofuinG: If thereis noalarmyetforv, setonefortimeT+l(u;v). Ifv's alarmis setforlaterthanT+l(u;v), thenresetit 's algorithmcomputesdistancesinanygraphwith positiveintegraledgelengths. Itisalmostreadyforuse, exceptthatweneedtosomehowimplementthesys temofalarms. Therightdatastructureforthisjobisapriori tyqueue(usuallyimplementedviaaheap), which maintainsa setofelements(nodes)withassociatednumeri ckeyvalues(alarmtimes) a standardbutis a littlemisleading:thepriorityqueuetypical lydoesnotitselfchangekeyvalues.

8 Whatthisprocedurereallydoesis tonotifythequeuethata wavefronts. G:ABS20010050G0:SABS. Dasgupta, , , andremoveit priorityqueueoutofthegivenelements, withthegivenkeyvalues. (Inmanyimplementations, thisissigni cantlyfasterthaninsertingtheelementsoneb yone.)The rsttwoletussetalarms, andthethirdtellsuswhich alarmisnexttogooff. Puttingthisalltogether, wegetDijkstra's algorithm( ).Inthecode,dist(u) referstothecurrentalarmclock settingfornodeu. A valueof1meansthealarmhasn' specialarray,prev, thatholdsonecrucialpieceofinformationfor each nodeu: theidentityofthenodeimmediatelybeforeito ntheshortestpathfromstou. Byfollowingtheseback-pointers, wecaneasilyreconstructshortestpaths, andsothisarray is a compactsummaryof fullexampleof thealgorithm's operation,alongwiththe nalshortest-pathtree, is , wecanthinkofDijkstra's algorithmasjustBFS, exceptit usesa priorityqueueinsteadofa regularqueue, soastoprioritizenodesina way concreteappreciationofhowandwhythealgori thmworks, butthereis a moredirect,moreabstractderivationthatdoe sn' nowstartfromscratch 's (G;l;s)Input:GraphG= (V;E), directedor undirected;positiveedgelengthsfle:e2Eg; vertexs2 VOutput:Forall verticesureachablefroms, dist(u) is setto the allu2V:dist(u) =1prev(u) =nildist(s) = 0H=makequeue(V)(usingdist-valuesas keys)whileHis notempty:u=deletemin(H)for all edges(u;v)2E:if dist(v)>dist(u) +l(u;v):dist(v) =dist(u) +l(u;v)prev(v) =udecreasekey(H.)

9 V) completerunofDijkstra's algorithm, :0D:1B:4E:1C:2 BCDEA424135213A:0D:6B:3E:7C:2 BCDEA413241352A:0D:5B:3E:6C:2 BCDEA413215234A:0D:5B:3E:6C:2 BCDEA2132S. Dasgupta, , knownshortestpaths. !"#$%&'(()**+,, 's a planforcomputingshortestpaths:expandoutw ardfromthestartingpoints, steadilygrowingtheregionof thegraphtowhich , rstincorporatingtheclosestnodesandthenmo vingontothosefurtheraway. Moreprecisely, whenthe knownregion is somesubsetofverticesRthatincludess,thene xtadditiontoit shouldbethenodeoutsideRthatis closesttos. Letuscallthisnodev;thequestionis:howdowe identifyit?To answer, consideru, thenodejustbeforevintheshortestpathfroms tov:234567vusSinceweareassumingthatalled gelengthsarepositive,umustbeclosertostha nvis. Thismeansthatuis inR otherwiseit wouldcontradictv's statusastheclosestnodetosoutsideR. So, theshortestpathfromstovis simplya knownshortestpathextendedbya ( );which oftheseidenti esv?

10 Theansweris,theshortestoftheseextendedpa ths. Because, if anevenshortersingle-edge-extendedpathexi sted,thiswouldoncemorecontradictv's statusasthenodeoutsideRclosesttos. So, it's easyto ndv: it isthenodeoutsideRforwhich thesmallestvalueofdistance(s;u) +l(u;v)is attained,asurangesoverR. Inotherwords,tryallsingle-edgeextensions of thecurrently knownshortestpaths, ndtheshortestsuch extendedpath, nowhaveanalgorithmforgrowingRbylookingat extensionsofthecurrentsetofshortestpaths . Someextraef ciencycomesfromnoticingthatonanygivenite ration,theonlynewextensionsarethoseinvol vingthenodemostrecentlyaddedtoregionR. ,dist(v)isthelengthofthecurrentlyshortes tsingle-edge-extendedpathleadingtov; it (s)to 0, otherdist( )valuesto1R=f g(the knownregion )whileR6=V:Pickthe nodev62 Rwithsmallestdist( )AddvtoRfor all edges(v;z)2E:if dist(z)>dist(v) +l(v;z):dist(z) =dist(v) +l(v;z)Incorporatingpriorityqueueoperati onsgivesusback Dijkstra's algorithm( ).