Unformatted text preview:

Algorithm simulation activityDijkstra’s algDijkstra’s alg - codeShortest paths from Homer, NYDijkstra activityKruskall’s Minimum Spanning Tree algKruskall’s alg - codeAir distance between cities in Statute milesNodes of Minimum Spanning TreeKruskall activity(reverse) Topological Sort algTop sort ActivityAlgorithm simulation activityDijkstra’s algSingleSourceShortestPath (directed graph G,vertex v)Distance is the best-known distance from v to each vertex.Set Distance= for each vertex, except Distance(v)=0Repeat until all vertices doneTake the vertex with the shortest distance (first will be v)Mark that it’s doneSee if there are any shorter routes to vertices that have edges from v.If so, update them with the shorter routeDijkstra’s alg - codeSingleSourceShortestPath (directed graph G,vertex v)set of nodes Uforeach vertex v in GDistance(v) = insert(U,v)endforDistance(S) = 0{ Distance could be implemented using a heap }repeat |G| timesv = vertex with smallest Distance(v)delete(U,v)foreach neighbor w of v doif member(U,w) thenDistance(w)=min(Distance(w), Distance(v)+Cost(v,w)endifendforendrepeatShortest paths from Homer, NY0123456789Dijkstra activity•Simulate Dijkstra’s Single Source Shortest Paths algorithm to find the shortest paths from Homer, NY (using the graph of the highways around Homer in New York).•As you run the algorithm, write on the graph to make pointers along the shortest paths.•You can record current distances, and “mark” (circle) nodes using the supplied table.•Optionally use a Heap to find the least Distance(v)Kruskall’s Minimum Spanning Tree algMinSpanTree (undirected graph G)Put all edges in G in a priority queueRemove all edges from G, and think of the nodesas a bunch of unconnected componentsWhile there is more than 1 component doGet the least-cost edge <u,v> from the priority queueIf nodes u and v are in different componentsMerge them into the same oneAdd edge <u,v> into the edges of themin spanning treeNote we have 1 less componentEndifEndwhileKruskall’s alg - codeMinSpanTree (undirected graph G)E=edges in GV=vertices in Gset of unconnected component CC=V { each vertex is its own component }int numC=|V| { # of unnconnected components }priority queue EQinsert all edges in E into EQwhile numC > 1 do<u,v>=EQ.DeleteMinU=Find(u)V=Find(v)if U  V thenUnion(U,V)<u,v> is an edge in the min span treenumC = numC - 1endifendwhileAir distance between cities in Statute milesSource: infoplease.com, Encyclopaedia Brittanica, National Geodetic SurveySan FranLos AngelesLondon Paris Tokyo ShanghaiSan Fran - 347 5357 5558 5135 6140Los Angeles- 5382 5588 5433 6438London - 213 5940 5715Paris - 6034 5754Tokyo - 1097Shanghai -Nodes of Minimum Spanning TreeS a nF r a n c i s c oL o sA n g e l e sT o k y oS h a n g h a iP a r i sL o n d o nUse boxes to write Up-Tree parentKruskall activity•Simulate Kruskall’s algorithm using Up-Trees to find the minimum spanning tree for the cities given.(reverse) Topological Sort algTopSort (DAG G)foreach vertex v in GMark vTopSort2 (G,v)endforTopSort2 (DAG G,vertex v)foreach edge <v,w> in GTopSort (G,w)endforprint vTop sort Activity3 2 11 4 33 2 23 2 63 4 13 7 84 0 14 2 1E t h i c s i nC S EA d v a n c e dC o m p u t a t i o n a lE t h i c s•Run TopSort on this graph (or as much of it as you feel is necessary)•Try to pick random nodes to visit first (to see why the alg


View Full Document

UW CSE 326 - Algorithm simulation activity

Download Algorithm simulation activity
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 Algorithm simulation activity 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 Algorithm simulation activity 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?