DOC PREVIEW
UW CSE 332 - Shortest Paths

This preview shows page 1-2-16-17-18-34-35 out of 35 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 35 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 35 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 35 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 35 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 35 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 35 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 35 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 35 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Slide 1Single source shortest pathsNot as easyDijkstra’s AlgorithmDijkstra’s Algorithm: IdeaThe AlgorithmImportant featuresExample #1Example #1Example #1Example #1Example #1Example #1Example #1Example #1Example #1Example #2Example #2Example #2Example #2Example #2Example #2Example #2Example #2Example #3Example #3Where are we?Correctness: IntuitionCorrectness: The Cloud (Rough Idea)Efficiency, first approachImproving asymptotic running timeImproving (?) asymptotic running timeEfficiency, second approachDense vs. sparse againWhat comes next?CSE332: Data AbstractionsLecture 17: Shortest PathsDan GrossmanSpring 2010Single source shortest paths•Done: BFS to find the minimum path length from v to u in O(|E|)•Actually, can find the minimum path length from v to every node –Still O(|E|)–No faster way for a “distinguished” destination in the worst-case•Now: Weighted graphs Given a weighted graph and node v, find the minimum-cost path from v to every node •As before, asymptotically no harder than for one destination•Unlike before, BFS will not workSpring 2010 2CSE332: Data AbstractionsNot as easyWhy BFS won’t work: Shortest path may not have the fewest edges–Annoying when this happens with costs of flightsSpring 2010 3CSE332: Data Abstractions500100100 100100We will assume there are no negative weights•Problem is ill-defined if there are negative-cost cycles•Next algorithm we will learn is wrong if edges can be negative–See homework710 5-11Dijkstra’s Algorithm•Named after its inventor Edsger Dijkstra (1930-2002)–Truly one of the “founders” of computer science; this is just one of his many contributions–Many people have a favorite Dijkstra story, even if they never met him–My favorite quotation: “computer science is no more about computers than astronomy is about telescopes”•The idea: reminiscent of BFS, but adapted to handle weights–A priority queue will prove useful for efficiency (later)–Will grow the set of nodes whose shortest distance has been computed–Nodes not in the set will have a “best distance so far”Spring 2010 4CSE332: Data AbstractionsDijkstra’s Algorithm: IdeaSpring 2010 5CSE332: Data Abstractions•Initially, start node has cost 0 and all other nodes have cost •At each step:–Pick closest unknown vertex v–Add it to the “cloud” of known vertices–Update distances for nodes with edges from v•That’s it! (Have to prove it produces correct answers)ABDCF HEG024 411222311023111719245The Algorithm1. For each node v, set v.cost =  and v.known = false2. Set source.cost = 03. While there are unknown nodes in the grapha) Select the unknown node v with lowest costb) Mark v as knownc) For each edge (v,u) with weight w, c1 = v.cost + w // cost of best path through v to u c2 = u.cost // cost of best path to u previously known if(c1 < c2){ // if the path through v is better u.cost = c1 u.path = v // for computing actual paths }Spring 2010 6CSE332: Data AbstractionsImportant features•Once a vertex is marked known, the cost of the shortest path to that node is known–As is the path itself•While a vertex is still not known, another shorter path to it might still be foundSpring 2010 7CSE332: Data AbstractionsExample #1Spring 2010 8CSE332: Data AbstractionsABDCF HEG0 2231102311171924vertex known? cost pathA 0B ??C ??D ??E ??F ??G ??H ??5Example #1Spring 2010 9CSE332: Data AbstractionsABDCF HEG02 412231102311171924vertex known? cost pathA Y 0B 2AC 1AD 4AE ??F ??G ??H ??5Example #1Spring 2010 10CSE332: Data AbstractionsABDCF HEG02 41122231102311171924vertex known? cost pathA Y 0B 2AC Y 1 AD 4AE 12CF ??G ??H ??5Example #1Spring 2010 11CSE332: Data AbstractionsABDCF HEG024 41122231102311171924vertex known? cost pathA Y 0B Y 2 AC Y 1 AD 4AE 12CF 4BG ??H ??5Example #1Spring 2010 12CSE332: Data AbstractionsABDCF HEG024 41122231102311171924vertex known? cost pathA Y 0B Y 2 AC Y 1 AD Y 4 AE 12CF 4BG ??H ??5Example #1Spring 2010 13CSE332: Data AbstractionsABDCF HEG024 741122231102311171924vertex known? cost pathA Y 0B Y 2 AC Y 1 AD Y 4 AE 12CF Y 4 BG ??H 7F5Example #1Spring 2010 14CSE332: Data AbstractionsABDCF HEG024 7411282231102311171924vertex known? cost pathA Y 0B Y 2 AC Y 1 AD Y 4 AE 12CF Y 4 BG 8HH Y 7 F5Example #1Spring 2010 15CSE332: Data AbstractionsABDCF HEG024 7411182231102311171924vertex known? cost pathA Y 0B Y 2 AC Y 1 AD Y 4 AE 11GF Y 4 BG Y 8 HH Y 7 F5Example #1Spring 2010 16CSE332: Data AbstractionsABDCF HEG024 7411182231102311171924vertex known? cost pathA Y 0B Y 2 AC Y 1 AD Y 4 AE Y 11 GF Y 4 BG Y 8 HH Y 7 F5Example #2Spring 2010 17CSE332: Data AbstractionsABCDFEG0212vertex known? cost pathA 0B ??C ??D ??E ??F ??G ??5111265310Example #2Spring 2010 18CSE332: Data AbstractionsABCDFEG021212vertex known? cost pathA Y 0B ??C£ 2 AD 1AE ??F ??G ??5111265310Example #2Spring 2010 19CSE332: Data AbstractionsABCDFEG0672126212vertex known? cost pathA Y 0B 6DC£ 2 AD Y 1 AE 2DF 7DG 6D5111265310Example #2Spring 2010 20CSE332: Data AbstractionsABCDFEG0642126212vertex known? cost pathA Y 0B 6DC Y 2 AD Y 1 AE 2DF 4CG 6D5111265310Example #2Spring 2010 21CSE332: Data AbstractionsABCDFEG0342126212vertex known? cost pathA Y 0B 3EC Y 2 AD Y 1 AE Y 2 DF 4CG 6D5111265310Example #2Spring 2010 22CSE332: Data AbstractionsABCDFEG0342126212vertex known? cost pathA Y 0B Y 3 EC Y 2 AD Y 1 AE Y 2 DF 4CG 6D5111265310Example #2Spring 2010 23CSE332: Data AbstractionsABCDFEG0342126212vertex known? cost pathA Y 0B Y 3 EC Y 2 AD Y 1 AE Y 2 DF Y 4 CG 6D5111265310Example #2Spring 2010 24CSE332: Data AbstractionsABCDFEG0342126212vertex known? cost pathA Y 0B Y 3 EC Y 2 AD Y 1 AE Y 2 DF Y 4 CG Y 6 D5111265310Example #3Spring 2010 25CSE332: Data AbstractionsYX11 1 19080 7060 50How will the best-cost-so-far for Y proceed?Is this expensive?…Example #3Spring 2010 26CSE332: Data AbstractionsYX11 1 19080 7060 50How will the best-cost-so-far for Y proceed? 90, 81, 72, 63, 54, …Is this expensive? No, each edge is processed only once…Where are we?•Have described Dijkstra’s algorithm–For single-source shortest paths in a weighted graph (directed or undirected) with no negative-weight edges–An example of a greedy algorithm: at each step, irrevocably does the best thing it can at that step•What should we do after learning an algorithm?–Prove


View Full Document

UW CSE 332 - Shortest Paths

Download Shortest Paths
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Shortest Paths and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Shortest Paths 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?