Algorithm simulation activity Dijkstra s alg SingleSourceShortestPath directed graph G vertex v Distance is the best known distance from v to each vertex Set Distance for each vertex except Distance v 0 Repeat until all vertices done Take the vertex with the shortest distance first will be v Mark that it s done See if there are any shorter routes to vertices that have edges from v If so update them with the shorter route Dijkstra s alg code SingleSourceShortestPath directed graph G vertex v set of nodes U foreach vertex v in G Distance v insert U v endfor Distance S 0 Distance could be implemented using a heap repeat G times v vertex with smallest Distance v delete U v foreach neighbor w of v do if member U w then Distance w min Distance w Distance v Cost v w endif endfor endrepeat Shortest paths from Homer NY 0 1 2 3 4 5 6 7 8 9 Dijkstra 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 alg MinSpanTree undirected graph G Put all edges in G in a priority queue Remove all edges from G and think of the nodes as a bunch of unconnected components While there is more than 1 component do Get the least cost edge u v from the priority queue If nodes u and v are in different components Merge them into the same one Add edge u v into the edges of the min spanning tree Note we have 1 less component Endif Endwhile Kruskall s alg code MinSpanTree undirected graph G E edges in G V vertices in G set of unconnected component C C V each vertex is its own component int numC V of unnconnected components priority queue EQ insert all edges in E into EQ while numC 1 do u v EQ DeleteMin U Find u V Find v if U V then Union U V u v is an edge in the min span tree numC numC 1 endif endwhile Source infoplease com Encyclopaedia Brittanica National Geodetic Survey Air distance between cities in Statute miles San Los London Fran Angeles Paris Tokyo Shanghai San Fran 347 5357 5558 5135 6140 Los Angeles 5382 5588 5433 6438 213 5940 5715 6034 5754 1097 London Paris Tokyo Shanghai Nodes of Minimum Spanning Tree Use boxes to write Up Tree parent San F r a n c is c o London P a r is Los A n g e le s T okyo Shanghai Kruskall activity Simulate Kruskall s algorithm using UpTrees to find the minimum spanning tree for the cities given reverse Topological Sort alg TopSort DAG G foreach vertex v in G Mark v TopSort2 G v endfor TopSort2 DAG G vertex v foreach edge v w in G TopSort G w endfor print v Top sort Activity 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 works 322 143 321 326 341 E th ic s in CSE 378 A dvanced C o m p u t a t io n a l E th ic s 421 401