392
Chapter9 GraphAlgorithms
void Graph::unweighted( Vertex s s )
{
Queue<Vertex> q;
for each Vertex v
v.dist = = INFINITY;
s.dist = = 0;
q.enqueue( s s );
while( !q.isEmpty( ( ) ) )
{
Vertex v v = = q.dequeue( ( );
for each h Vertex x w adjacent to v
if( w.dist == INFINITY )
{
w.dist = = v.dist t + 1;
w.path = = v;
q.enqueue( w );
}
}
}
Figure9.18 Psuedocodeforunweightedshortest-pathalgorithm
Wekeepallofthesameinformationasbefore.Thus,eachvertexismarkedaseither
known orunknown.A tentativedistanced
v
iskeptforeach vertex,asbefore.Thisdis-
tanceturnsouttobetheshortestpathlengthfromstovusingonlyknownverticesas
intermediates.Asbefore,werecordp
v
,whichisthelastvertextocauseachangetod
v
.
Thegeneralmethod tosolvethe single-source shortest-pathproblem m is knownas
Dijkstra’salgorithm.Thisthirty-year-oldsolutionisaprimeexampleofagreedyalgo-
rithm.Greedyalgorithmsgenerallysolveaprobleminstagesbydoingwhatappearsto
bethebestthing ateach stage.For example,tomake changein U.S.currency,most
peoplecountoutthequartersfirst,thenthedimes,nickels,andpennies.Thisgreedyalgo-
rithmgiveschangeusingtheminimumnumberofcoins.Themainproblemwithgreedy
algorithmsisthattheydonotalwayswork.Theadditionofa12-centpiecebreaksthe
coin-changingalgorithmforreturning15cents,becausetheansweritgives(one12-cent
pieceandthreepennies)isnotoptimal(onedimeandonenickel).
Dijkstra’salgorithmproceedsinstages,justliketheunweightedshortest-pathalgo-
rithm.Ateach stage,Dijkstra’salgorithmselectsavertex,v,whichhasthesmallestd
v
amongalltheunknownverticesanddeclaresthattheshortestpathfromstovisknown.
Theremainderofastageconsistsofupdatingthevaluesofd
w
.
Intheunweightedcase,wesetd
w
=d
v
+1ifd
w
=∞.Thus,weessentiallylowered
thevalueofd
w
ifvertexvofferedashorterpath.Ifweapplythesamelogictotheweighted
How to convert pdf to powerpoint slides - C# Create PDF from PowerPoint Library to convert pptx, ppt to PDF in C#.net, ASP.NET MVC, WinForms, WPF
Online C# Tutorial for Creating PDF from Microsoft PowerPoint Presentation
how to add pdf to powerpoint slide; and paste pdf into powerpoint
How to convert pdf to powerpoint slides - VB.NET Create PDF from PowerPoint Library to convert pptx, ppt to PDF in vb.net, ASP.NET MVC, WinForms, WPF
VB.NET Tutorial for Export PDF file from Microsoft Office PowerPoint
convert pdf file to powerpoint online; pdf into powerpoint
9.3 Shortest-PathAlgorithms
393
InitialState
v
3
Dequeued
v
1
Dequeued
v
6
Dequeued
v
known
d
v
p
v
known
d
v
p
v
known
d
v
p
v
known
d
v
p
v
v
1
F
0
F
1
v
3
T
1
v
3
T
1
v
3
v
2
F
0
F
0
F
2
v
1
F
2
v
1
v
3
F
0
0
T
0
0
T
0
0
T
0
0
v
4
F
0
F
0
F
2
v
1
F
2
v
1
v
5
F
0
F
0
F
0
F
0
v
6
F
0
F
1
v
3
F
1
v
3
T
1
v
3
v
7
F
0
F
0
F
0
F
0
Q:
v
3
v
1
,v
6
v
6
,v
2
,v
4
v
2
,v
4
v
2
Dequeued
v
4
Dequeued
v
5
Dequeued
v
7
Dequeued
v
known
d
v
p
v
known
d
v
p
v
known
d
v
p
v
known
d
v
p
v
v
1
T
1
v
3
T
1
v
3
T
1
v
3
T
1
v
3
v
2
T
2
v
1
T
2
v
1
T
2
v
1
T
2
v
1
v
3
T
0
0
T
0
0
T
0
0
T
0
0
v
4
F
2
v
1
T
2
v
1
T
2
v
1
T
2
v
1
v
5
F
3
v
2
F
3
v
2
T
3
v
2
T
3
v
2
v
6
T
1
v
3
T
1
v
3
T
1
v
3
T
1
v
3
v
7
F
0
F
3
v
4
F
3
v
4
T
3
v
4
Q:
v
4
,v
5
v
5
,v
7
v
7
empty
Figure9.19 Howthedatachangeduringtheunweightedshortest-pathalgorithm
case,thenweshouldsetd
w
=d
v
+c
v,w
ifthisnewvalueford
w
wouldbeanimprovement.
Putsimply,thealgorithmdecideswhetherornotitisagoodideatousevonthepathtow.
Theoriginalcost,d
w
,isthecostwithoutusingv;thecostcalculatedaboveisthecheapest
pathusingv(andonlyknownvertices).
ThegraphinFigure9.20isourexample.Figure9.21representstheinitialconfig-
uration,assumingthatthestartnode,s,isv
1
.Thefirstvertexselectedisv
1
,withpath
length0.Thisvertexismarkedknown.Nowthatv
1
isknown, someentriesneedtobe
adjusted.Theverticesadjacenttov
1
arev
2
andv
4
.Boththeseverticesgettheirentries
adjusted,asindicatedinFigure9.22.
Next,v
4
isselectedandmarkedknown.Verticesv
3
,v
5
,v
6
,andv
7
areadjacent,andit
turnsoutthatallrequireadjusting,asshowninFigure9.23.
Next,v
2
isselected.v
4
isadjacentbutalreadyknown,sonoworkisperformedonit.
v
5
isadjacentbutnotadjusted,becausethecostofgoingthroughv
2
is2+10=12and
apathoflength3isalreadyknown.Figure9.24showsthetableaftertheseverticesare
selected.
C# PowerPoint - How to Process PowerPoint
Microsoft PowerPoint Document Processing Control in Visual C#.NET of RasterEdge .NET Imaging SDK is a reliable and professional PowerPoint slides/pages editing
how to change pdf to powerpoint on; changing pdf to powerpoint
VB.NET PowerPoint: Process & Manipulate PPT (.pptx) Slide(s)
add image to slide, extract slides and merge library SDK, this VB.NET PowerPoint processing control powerful & profession imaging controls, PDF document, image
pdf to ppt converter online for large; how to convert pdf into powerpoint presentation
394
Chapter9 GraphAlgorithms
6
2
4
1
3
10
2
4
8
5
1
2
v
1
v
2
v
3
v
4
v
5
v
6
v
7
Figure9.20 ThedirectedgraphG(again)
v
known
d
v
p
v
v
1
F
0
0
v
2
F
0
v
3
F
0
v
4
F
0
v
5
F
0
v
6
F
0
v
7
F
0
Figure9.21 InitialconfigurationoftableusedinDijkstra’salgorithm
v
known
d
v
p
v
v
1
T
0
0
v
2
F
2
v
1
v
3
F
0
v
4
F
1
v
1
v
5
F
0
v
6
F
0
v
7
F
0
Figure9.22 Afterv
1
isdeclaredknown
Thenextvertexselectedisv
5
atcost3.v
7
istheonlyadjacentvertex,butitisnot
adjusted,because3+6>5.Thenv
3
isselected,andthedistanceforv
6
isadjusteddown
to3+5=8.TheresultingtableisdepictedinFigure9.25.
Next,v
7
is selected;v
6
gets updateddown to 5+1 1 = 6.Theresulting g table is
Figure9.26.
VB.NET PowerPoint: Sort and Reorder PowerPoint Slides by Using VB.
clip art or screenshot to PowerPoint document slide large amount of robust PPT slides/pages editing powerful & profession imaging controls, PDF document, image
how to change pdf to powerpoint format; convert pdf file into ppt
VB.NET PowerPoint: Use PowerPoint SDK to Create, Load and Save PPT
Besides, users also can get the precise PowerPoint slides count as soon as the PowerPoint document has been loaded by using the page number getting method.
how to convert pdf to powerpoint in; how to convert pdf to powerpoint on
9.3 Shortest-PathAlgorithms
395
v
known
d
v
p
v
v
1
T
0
0
v
2
F
2
v
1
v
3
F
3
v
4
v
4
T
1
v
1
v
5
F
3
v
4
v
6
F
9
v
4
v
7
F
5
v
4
Figure9.23 Afterv
4
isdeclaredknown
v
known
d
v
p
v
v
1
T
0
0
v
2
T
2
v
1
v
3
F
3
v
4
v
4
T
1
v
1
v
5
F
3
v
4
v
6
F
9
v
4
v
7
F
5
v
4
Figure9.24 Afterv
2
isdeclaredknown
v
known
d
v
p
v
v
1
T
0
0
v
2
T
2
v
1
v
3
T
3
v
4
v
4
T
1
v
1
v
5
T
3
v
4
v
6
F
8
v
3
v
7
F
5
v
4
Figure9.25 Afterv
5
andthenv
3
aredeclaredknown
Finally,v
6
isselected.ThefinaltableisshowninFigure9.27.Figure9.28graphically
showshowedgesaremarkedknownandverticesupdatedduringDijkstra’salgorithm.
Toprintouttheactualpathfromastartvertextosomevertexv,wecanwritearecursive
routinetofollowthetrailleftinthepvariables.
WenowgivepseudocodetoimplementDijkstra’salgorithm.Each
Vertex
storesvarious
datamembersthatareusedinthealgorithm.ThisisshowninFigure9.29.
VB.NET PowerPoint: Extract & Collect PPT Slide(s) Using VB Sample
want to combine these extracted slides into a please read this VB.NET PowerPoint slide processing powerful & profession imaging controls, PDF document, image
convert pdf to powerpoint presentation; convert pdf back to powerpoint
VB.NET PowerPoint: Merge and Split PowerPoint Document(s) with PPT
of the split PPT document will contain slides/pages 1-4 code in VB.NET to finish PowerPoint document splitting If you want to see more PDF processing functions
convert pdf to powerpoint online no email; pdf to powerpoint converter online
396
Chapter9 GraphAlgorithms
v
known
d
v
p
v
v
1
T
0
0
v
2
T
2
v
1
v
3
T
3
v
4
v
4
T
1
v
1
v
5
T
3
v
4
v
6
F
6
v
7
v
7
T
5
v
4
Figure9.26 Afterv
7
isdeclaredknown
v
known
d
v
p
v
v
1
T
0
0
v
2
T
2
v
1
v
3
T
3
v
4
v
4
T
1
v
1
v
5
T
3
v
4
v
6
T
6
v
7
v
7
T
5
v
4
Figure9.27 Afterv
6
isdeclaredknownandalgorithmterminates
ThepathcanbeprintedoutusingtherecursiveroutineinFigure9.30.Theroutine
recursivelyprintsthepathallthewayuptothevertexbeforevonthepath,andthenjust
printsv.Thisworksbecausethepathissimple.
Figure9.31showsthemainalgorithm,whichisjusta
for
looptofillupthetableusing
thegreedyselectionrule.
Aproofbycontradictionwillshowthatthisalgorithmalwaysworksaslong asno
edgehasanegativecost.Ifanyedgehasnegativecost,thealgorithmcouldproducethe
wronganswer(seeExercise9.7(a)).Therunningtimedependsonhowtheverticesare
manipulated,whichwehaveyettoconsider.Ifweusetheobviousalgorithmofsequentially
scanningtheverticestofindtheminimumd
v
,eachphasewilltakeO(|V|)timetofindthe
minimum,andthusO(|V|
2
)timewillbespentfindingtheminimumoverthecourseofthe
algorithm.Thetimeforupdatingd
w
isconstantperupdate,andthereisatmostoneupdate
peredgeforatotalofO(|E|).Thus,thetotalrunningtimeisO(|E|+|V|
2
)=O(|V|
2
).Ifthe
graphisdense,with|E|=(|V|
2
),thisalgorithmisnotonlysimplebutalsoessentially
optimal,sinceitrunsintimelinearinthenumberofedges.
Ifthegraphissparse,with|E|=(|V|),thisalgorithmistooslow.Inthiscase,the
distanceswouldneedtobekeptinapriorityqueue.Thereareactuallytwowaystodothis;
botharesimilar.
VB.NET PowerPoint: Complete PowerPoint Document Conversion in VB.
VB.NET PowerPoint Conversion Control to render and convert target PowerPoint document to various image or document formats, such as PDF, BMP, TIFF
convert pdf to powerpoint with; convert pdf into ppt online
VB.NET PowerPoint: Convert & Render PPT into PDF Document
Using this VB.NET PowerPoint to PDF converting demo code below, you can easily convert all slides of source PowerPoint document into a multi-page PDF file.
pdf to powerpoint; convert pdf to powerpoint slide
9.3 Shortest-PathAlgorithms
397
6
2
4
1
3
10
2
4
8
5
1
2
6
2
4
1
3
10
2
4
8
5
1
2
6
2
4
1
3
10
2
4
8
5
1
2
6
2
4
1
3
10
2
4
8
5
1
2
6
2
4
1
3
10
2
4
8
5
1
2
6
2
4
1
3
10
2
4
8
5
1
2
6
2
4
1
3
10
2
4
8
5
1
2
6
2
4
1
3
10
2
4
8
5
1
2
0
2
0
1
2
0
3
1
3
5
9
2
0
1
3
3
5
9
3
2
0
3
1
3
5
9
2
0
1
3
5
8
3
2
0
3
1
3
5
6
2
0
1
3
5
6
v
1
v
2
v
3
v
4
v
5
v
6
v
7
v
1
*
v
2
v
3
v
4
v
5
v
6
v
7
v
1
*
v
2
v
3
v
4
*
v
5
v
6
v
7
v
1
*
v
2
*
v
3
v
4
*
v
5
v
6
v
7
v
1
*
v
2
*
v
3
v
4
*
v
5
*
v
6
v
7
v
1
*
v
2
*
v
3
*
v
4
*
v
5
*
v
6
v
7
v
1
*
v
2
*
v
3
*
v
4
*
v
5
*
v
6
v
7
*
v
1
*
v
2
*
v
3
*
v
4
*
v
5
*
v
6
*
v
7
*
Figure9.28 StagesofDijkstra’salgorithm
Selectionofthevertexvisa
deleteMin
operation,sinceoncetheunknownminimum
vertexisfound,itisnolongerunknownandmustberemovedfromfutureconsideration.
Theupdateofw’sdistancecanbeimplementedtwoways.
Onewaytreatstheupdateasa
decreaseKey
operation.Thetimetofindtheminimumis
thenO(log|V|),asisthetimetoperformupdates,whichamountto
decreaseKey
operations.
ThisgivesarunningtimeofO(|E|log|V|+|V|log|V|)=O(|E|log|V|),animprovement
VB.NET PowerPoint: Add Image to PowerPoint Document Slide/Page
insert or delete any certain PowerPoint slide without methods to reorder current PPT slides in both powerful & profession imaging controls, PDF document, tiff
images from pdf to powerpoint; how to change pdf to ppt on
C# PowerPoint: C# Guide to Add, Insert and Delete PPT Slide(s)
file and it includes all slides and properties to view detailed guide for each PowerPoint slide processing & profession imaging controls, PDF document, tiff
convert pdf to powerpoint online for; pdf to ppt converter online
398
Chapter9 GraphAlgorithms
/**
* PSEUDOCODE sketch h of the e Vertex x structure.
* In real C++, , path would be of f type e Vertex *,
* and d many of the code fragments that we describe
* require either r a dereferencing * * or r use the
* -> operator r instead of the e . . operator.
* Needless s to say, this s obscures s the basic c algorithmic c ideas.
*/
struct Vertex
{
List
adj;
// Adjacency y list
bool
known;
DistType dist;
// DistType is probably y int
Vertex
path;
// Probably Vertex *, as mentioned d above
// Other data and d member r functions s as needed
};
Figure9.29 VertexclassforDijkstra’salgorithm(pseudocode)
/**
* Print t shortest path to v v after r dijkstra has s run.
* Assume e that the path exists.
*/
void Graph::printPath( Vertex x v v )
{
if( v.path != NOT_A_VERTEX )
{
printPath( v.path h );
cout << " to ";
}
cout << v;
}
Figure9.30 Routinetoprinttheactualshortestpath
overthepreviousboundforsparsegraphs.Sincepriorityqueuesdonotefficientlysupport
the
find
operation,thelocationinthepriorityqueueofeachvalueofd
i
willneedtobe
maintainedandupdatedwheneverd
i
changesinthepriorityqueue.Ifthepriorityqueue
isimplementedbyabinaryheap,thiswillbemessy.Ifapairingheap(Chapter12)isused,
thecodeisnottoobad.
Analternatemethodistoinsertwandthenewvalued
w
intothepriorityqueueevery
timew’sdistancechanges.Thus,theremaybemorethanonerepresentativeforeachvertex
in thepriority queue.Whenthe
deleteMin
operationremoves thesmallestvertex from
thepriorityqueue,itmustbecheckedtomakesurethatitisnotalreadyknownand,if
9.3 Shortest-PathAlgorithms
399
void Graph::dijkstra( Vertex s s )
{
for each Vertex x v
{
v.dist = = INFINITY;
v.known = false;
}
s.dist = 0;
while( there e is an unknown distance e vertex x )
{
Vertex v v = = smallest t unknown distance e vertex;
v.known = true;
for each Vertex x w adjacent to v
if( !w.known )
{
DistType cvw = = cost t of f edge e from v to w;
if( v.dist t + cvw < w.dist t )
{
// Update e w
decrease( w.dist to v.dist t + + cvw w );
w.path = v;
}
}
}
}
Figure9.31 PseudocodeforDijkstra’salgorithm
itis,itissimplyignoredandanother
deleteMin
isperformed.Althoughthismethodis
superiorfromasoftwarepointofview,andiscertainlymucheasiertocode,thesizeof
thepriorityqueuecouldgettobeaslargeas|E|.Thisdoesnotaffecttheasymptotictime
bounds,since|E|≤|V|
2
impliesthatlog|E|≤2log|V|.Thus,westillgetanO(|E|log|V|)
algorithm.However,thespacerequirementdoesincrease,andthiscouldbeimportantin
someapplications.Moreover,becausethismethodrequires|E|
deleteMin
sinsteadofonly
|V|,itislikelytobeslowerinpractice.
Noticethatforthetypicalproblems,suchascomputermailandmasstransitcom-
mutes,thegraphsaretypicallyverysparsebecausemostverticeshaveonlyacoupleof
edges,soitisimportantinmanyapplicationstouseapriorityqueuetosolvethisproblem.
TherearebettertimeboundspossibleusingDijkstra’salgorithmifdifferentdatastruc-
turesareused.InChapter11,wewillseeanotherpriorityqueuedatastructurecalledthe
400
Chapter9 GraphAlgorithms
Fibonacciheap.Whenthisisused,therunningtimeisO(|E|+|V|log|V|).Fibonacciheaps
havegoodtheoreticaltimeboundsbutafairamountofoverhead,soitisnotclearwhether
usingFibonacciheapsisactuallybetterinpracticethanDijkstra’salgorithmwithbinary
heaps.Todate,therearenomeaningfulaverage-caseresultsforthisproblem.
9.3.3 GraphswithNegativeEdgeCosts
Ifthegraphhasnegativeedgecosts,thenDijkstra’salgorithmdoesnotwork.Theproblem
isthatonceavertex,u,isdeclaredknown, itispossiblethatfromsomeotherunknown
vertex,v,thereisapathbacktouthatisverynegative.Insuchacase,takingapathfrom
stovbacktouisbetterthangoingfromstouwithoutusingv.Exercise9.7(a)asksyouto
constructanexplicitexample.
Atemptingsolutionistoaddaconstanttoeachedgecost,thusremovingnegative
edges,calculateashortestpathonthenewgraph,andthenusethatresultontheoriginal.
Thenaiveimplementationofthisstrategydoesnotworkbecausepathswithmanyedges
becomemoreweightythanpathswithfewedges.
Acombinationoftheweightedandunweightedalgorithmswillsolvetheproblem,but
atthecostofadrasticincreaseinrunningtime.Weforgetabouttheconceptofknown
vertices,sinceouralgorithmneedstobeabletochangeitsmind.Webeginbyplacings
onaqueue.Then,ateachstage,wedequeueavertexv.Wefindallverticeswadjacent
tovsuchthatd
w
d
v
+c
v,w
.Weupdated
w
andp
w
,andplacewonaqueueifitisnot
alreadythere.Abitcanbesetforeachvertextoindicatepresenceinthequeue.Werepeat
theprocessuntilthequeueisempty.Figure9.32(almost)implementsthisalgorithm.
Although the algorithmworksifthere arenonegative-cost cycles, , it is nolonger
true that thecodein theinner
for
loop is executed onceper edge. . Each h vertex x can
dequeueatmost|V|times,sotherunningtimeisO(|E|·|V|)ifadjacencylistsareused
(Exercise9.7(b)).This is quiteanincreasefromDijkstra’s algorithm,soit is fortunate
that,inpractice,edgecostsarenonnegative.Ifnegative-costcyclesarepresent,thenthe
algorithmaswrittenwillloopindefinitely.Bystoppingthealgorithmafteranyvertexhas
dequeued|V|+1times,wecanguaranteetermination.
9.3.4 AcyclicGraphs
Ifthegraphisknown tobeacyclic,we canimproveDijkstra’salgorithmby changing
theorderinwhichverticesaredeclaredknown,otherwiseknownasthevertexselection
rule.Thenewruleistoselectverticesintopologicalorder.Thealgorithmcanbedonein
onepass,sincetheselectionsandupdatescantakeplaceasthetopologicalsortisbeing
performed.
Thisselectionruleworks becausewhen avertexvisselected,itsdistance,d
v
,can
nolongerbelowered,sincebythetopologicalorderingruleit hasnoincoming edges
emanatingfromunknownnodes.
Thereis noneedforapriorityqueuewith thisselectionrule;therunning timeis
O(|E|+|V|),sincetheselectiontakesconstanttime.
Anacyclicgraphcouldmodelsomedownhillskiingproblem—wewanttogetfrom
pointatob,butcanonlygodownhill,soclearlytherearenocycles.Anotherpossible
9.3 Shortest-PathAlgorithms
401
void Graph::weightedNegative( Vertex s s )
{
Queue<Vertex> q;
for each Vertex x v
v.dist = = INFINITY;
s.dist = 0;
q.enqueue( s s );
while( !q.isEmpty( ( ) ) )
{
Vertex v v = = q.dequeue( );
for each Vertex x w adjacent to v
if( v.dist t + + cvw < < w.dist t )
{
// Update w
w.dist = = v.dist + + cvw;
w.path = = v;
if( w w is not already in q q )
q.enqueue( w w );
}
}
}
Figure9.32 Pseudocodeforweightedshortest-pathalgorithmwithnegativeedgecosts
applicationmightbethemodelingof(nonreversible)chemicalreactions.Wecouldhave
eachvertexrepresentaparticularstateofanexperiment.Edgeswouldrepresentatransi-
tionfromonestatetoanother,andtheedgeweightsmightrepresenttheenergyreleased.
Ifonlytransitionsfromahigherenergystatetoalowerareallowed,thegraphisacyclic.
A more e important use of acyclic graphs is critical path analysis. The graph h in
Figure9.33willserveasourexample.Eachnoderepresentsanactivitythatmustbeper-
formed,alongwiththetimeittakestocompletetheactivity.Thisgraphisthusknownas
anactivity-nodegraph.Theedgesrepresentprecedencerelationships:Anedge(v,w)means
thatactivityvmustbecompletedbeforeactivitywmaybegin.Ofcourse,thisimpliesthat
thegraphmustbeacyclic.Weassumethatanyactivitiesthatdonotdepend(eitherdirectly
orindirectly)oneachothercanbeperformedinparallelbydifferentservers.
Thistypeofagraphcouldbe(andfrequentlyis)usedtomodelconstructionprojects.
Inthiscase,thereareseveralimportantquestionswhichwouldbeofinteresttoanswer.
First,whatistheearliestcompletiontimefortheproject?Wecanseefromthegraphthat10
timeunitsarerequiredalongthepathA,C,F,H.Anotherimportantquestionistodeter-
minewhichactivitiescanbedelayed,andbyhowlong,withoutaffectingtheminimum
completiontime.Forinstance,delayinganyofA,C,F,orHwouldpushthecompletion
Documents you may be interested
Documents you may be interested