New User Special Price Expires in

Let's log you in.

Sign in with Facebook


Don't have a StudySoup account? Create one here!


Create a StudySoup account

Be part of our community, it's free to join!

Sign up with Facebook


Create your account
By creating an account you agree to StudySoup's terms and conditions and privacy policy

Already have a StudySoup account? Login here


by: Mrs. Rahul Wuckert
Mrs. Rahul Wuckert
GPA 3.78


Almost Ready


These notes were just uploaded, and will be ready to view shortly.

Purchase these notes here, or revisit this page.

Either way, we'll remind you when they're ready :)

Preview These Notes for FREE

Get a free preview of these Notes, just enter your email below.

Unlock Preview
Unlock Preview

Preview these materials now for free

Why put in your email? Get access to more of this material and other relevant free materials for your school

View Preview

About this Document

Class Notes
25 ?




Popular in Course

Popular in Comm Sciences and Disorders

This 34 page Class Notes was uploaded by Mrs. Rahul Wuckert on Thursday September 17, 2015. The Class Notes belongs to CIS 4900 at Florida State University taught by Staff in Fall. Since its upload, it has received 58 views. For similar materials see /class/205700/cis-4900-florida-state-university in Comm Sciences and Disorders at Florida State University.

Popular in Comm Sciences and Disorders


Reviews for DIS


Report this Material


What is Karma?


Karma is the currency of StudySoup.

You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 09/17/15
M Dijkstra39s Algori rhm for Single Source Shor res r Pa rh Problem Programming Puzzles and Compe ri rions CIS 4900 5920 Spring 2009 OuTline Dijks rro39s olgori rhm How To code if in Java An opplico rion To a problem on The FSU ACM spring 2009 programming conTeST PoinTTopoin r Shor res r Pa rh Problem PoinTTopoin r Shor res r Pa rh Problem Dij ks rr39a39s Idea 2 Se led Q x priorfy queue I nearesf un5e7 fea neghbor of X I Shor fesf disTance from s To all nodes iniTially unsa fled Shor fesf disTance To s is zero TenTaTive disTance To oTher39s is 0 PM all nodes in queue ordered by TenTaTive disTance from s Take ouT near39esT unSeTTled node x Se le ifs disTance from s For39 each unSeTTled immedia re neighbor y of x If going from s To y Through x is shor39Ter39 Than shortest path Thr ough Se led nodes updaTe TenTaTive disTance To y Repea r from sTep 4 unTil disTance To desTinaTion is Se led VX e v dx so se r rled a J ltv Q V ds rorquotr O VlogV while Q i Q choose x c Q To minimize dx 09V Q Q x Iogv if xdes r br39eok se r rled se r rled U X dX39553970r7 esf dsfance fox for39 each unse r rled neighbor y of x if dygtgtdxgt Iengtltygtgt do dgtlt Iengtltygt backm x ElogV prior7y queue To ex rrac r pa rh 1 Trace backlinks from des rina rion To source reversing Them as we go 2 Traverse reversed links from source To des rina rion To ob rain a shor res r pa rh lt back lt back lt back back 0 back 0 back To ge r minimal spanning Tr39ee Run un ril all nodes are se r rled Reverse all links Example Applica rion Problem from Spring 2009 FSU local ACM programming con res r h r rpwwwcsf5uedubakerpcci ryf5u0409con res rpdf Imaginary ci ry is grid of squares Special rules abou r direc rion of Travel be rween squares 39 Find shor res r pa rh be rween Two secified poin rs Movemen r Rules Exampe for n4 0 1 2 3 4 5 6 7 8 9 1O 11 12 13 14 15 Fr39omblockx xmodnO gtmaymoveNor39S xmodn1 gtmaymoveNEor39SW xmodn2 gtmaymoveEor39W xmodn3 gtmaymoveNWor39SE Movemen r r39ules l l xmodn2 gtmaymoveEor39W xmodn3 gtmay move NWor39 SE w Read problem again Ths exampe Is Meanssfer MM 16 rue Assume 16 error 5 in le exampe Ask Me judge For39 example suppose n4 If you are currently in block 8 you may move To block 4 and 12 If you are in block 5 you may move To block 2 and 8 If you are in block 10 you may move To block 7 and 13 If you are in block 11 you may move To block 6 No re Tha r you may move ro only one neighboring block if The other block does no r exis rquot Designing a Java implemen ra rion How To r39epr39esen r nodes class Too cumbersome for39 Time limi r so use in reger39s 0 V1 for V n n How To r39epr39esen r edges How To r39epr39esen r distance How To implemen r Q Edge represen ra rion Adjacency lis r is mos r efficien r Avoids looking a r nonedges Reduces from OV2ogV To OEogV How To implemen r an adjacency lis r Simple special case In This case number of edges per39 node seems limiTed To 2 inT neighbor39 new inTV2 neighbor39x0 fir39sT neighbor neighbor39x1 second neighbor WhoT if less Than Two edges neighbor39xi 1 buT now we need To check for39 This case 2290f for in r x O x lt V x WW swi rch x 70 n case 0 if xn gt 0 neighborx0 xn N if xn lt V neighbor39x1 xn 5 break case 1 if xn gt 0 ampamp x quot0 n lt n1 neighbor39x0 xn1 NE if xn lt N ampamp x quot0 n gt 0 neighbor39x1 xn1 SW e rc Al rer39no rives array of arrays saves 1 check bu r need code To cr39eo re subor39r39oy of cor39r39ec r leng rh implici r r39epr39esen ro rion using a func rion or39 i rer39o ror39 eg in r neighbor39xi maybe a good idea bu r es rimo re of coding Time seems gr39eo rer39 How To represen r se r rled boolean se r rled new booleanV for i O i lt V i se r rledi false How To represen r dis rances in r d in rV How To represen r 0 for39 i0 i lt V i di In reger39MAXVALUE wa rch ou r for39 overflow Ia rer39 How To r39epr39esenT Q A Roll your39 own pr39ior39iTy queue B Use Java uTiliTy library Takes less Time To code no debugging Time if you know how To use iT 7 7 7 p3939a va sun comla vase a o csapV a vau fYPrbrI39nyLeue 7 7711 Se ing up prior7y queue ComparatomIn regew shor res rDis rance new ComparatomIn regewO public i M compareIn reger39 L In reger R if dL gt dR return 1 if dL lt dR return 1 if L gt R r39e rur39n 1 if L lt R r39e rur39n 1 r39e rur39n O H PrioriTyQueueltInTegergt q new Pr39ioriTyQueueltInTegergtN shor res rDis rance A 397 era codHg of ab5397 rac7 agorfhm Vx e V dx 2 00 se r rled Q for39 i O i lt V i di Infeger MAXVALUE se r rledi false Q V ds rarquotr O for39 i O i lt V i qaddi ds rar r O while Q 1 Q while qisEmpTy choose x c Q To minimize dx Q Q X x qpo if xdesT break seTTIed seTTIed U x seTTIedx True for each unseTTled neighbor y of x for inT i O i lt 2 i y neighbor39xi if i 1 ampamp seTTIedy if dYgtdgtlt 6ngtltY if dy1gtdx1 1 dy dx enxy39 dy dx139 backy x backy x Wmf s wrong wfh 7775 Q de rails Need To r39einser39T nodes in pr39ior39i ry queue when pr39ior39i ries change Does r39e inser39Tion require dele rion firs r Java documen ra rion does no r seem very clear39 on This bu r an experimen r shows Tha r r39epea red inser39Tion will cr39ea re duplica res while I qisEmp ry x qpo if xdes r break se r rledx True for39 in r i O i lt 2 i y neighbor39xi if i 1 ampamp se r rledy if dygtdgtlt 1 dY dgtlt1 backy x qr39emovey QGddO39 W a D Remo ve and refnsem nodes W wfh changed dSfance 5711pI39fy 39m397 39a39za7 3907 avoa w39s f hg dS39connecfea nodes for39 i O i lt V i di Infeger MAXVALUE se r rledi false for39 i O i lt V i qaddi qadds rarquotr ds rar r O We run program If fails 39 Fails To find my pa rh on given sample inpuT 16 99 5 Look a r sample ou rpu r 99 116 100 84 68 52 36 20 5 S rudy example in de rail Moduus See11539 W Z 5 W Z 3 W Z fobe4 afhen 0 1 6 7 8 910 11 12 131415 manV 16 17 22 23 24 25 26 27 28 29 30 31 32 33 38 39 40 41 42 43 44 45 46 47 48 49 54 55 56 57 58 59 60 61 62 63 20m0d40 64 65 70 71 72 73 74 75 76 77 78 79 5390 can ony move 80 81 86 87 88 89 90 91 92 93 94 95 7 0 N0r5 102103104105106107108109110111 118119120121122123124125126127 96 97 112 113 128129130131 132133134135136137138139140141142143 144145146147148149150151 152153154155156157158159 160161 162163164165166167168169170171172173174175 176177178179180181 182183184185186187188189190191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 5390 I39m em See11539 7 0 be fhaf edges are Q39a lfec ona Movemen r r39ules x mod n O gt may move N or39 5 1w1 or39 NW or39 NE w x mod n 1 gt may move NE or39 SW or39 E xmodn2 gtmaymoveEor39W or39SWor39SE xmodn3 gtmaymoveNWor39SE or39 W Seffng up negMW for m r x O x lt V x arrayby SWi I Ch X 00 new rues case 0 if xn gt 0 neighborx0 xn N if xn lt V neighbor39x1 xn S if xn gt 0 ampamp x quot0 n gt 0 neighborx2 xn1 NW if xn gt 0 ampamp x quot0 n lt n1 neighbor39x3 xn1 NE e rc Run program again Works OK on sample da ra We submi r i r To judge IT is repor red as failure Af rer con res r we ge r judge39s da ra and reTesT One of judge39s Thee da ra se rs seems broken In con res r you could never have found This ou r 397pu7 12 33 20 our oufpuf 33 44 31 30 41 52 39 38 49 60 72 84 96 108 120 judges oufpuf 33 34 4760 72 84 96 108 120 12 13 14 15 16 17 18 19 2O 21 22 23 24 25 26 27 37 1 29 116 117 u 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 WhaT have we learned DijksTr39a39s algor39iThm Use of javauTilPr39ior39iTyQueue SuleeTy of inser39TdeleTe Judges someTimes make misTakes iT can be our39 bad luck if we spend Too much Time on one problem I could noT have gone Through all This analysis during a conTesT Time frame Ful program wwwcsfsuedubakerpcciTyCi ryjava


Buy Material

Are you sure you want to buy this material for

25 Karma

Buy Material

BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.


You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

Why people love StudySoup

Bentley McCaw University of Florida

"I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

Anthony Lee UC Santa Barbara

"I bought an awesome study guide, which helped me get an A in my Math 34B class this quarter!"

Jim McGreen Ohio University

"Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

Parker Thompson 500 Startups

"It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

Become an Elite Notetaker and start selling your notes online!

Refund Policy


All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email


StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here:

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.