Subject: Design Analysis Algorithm

Given the following undirected, weighted graph. A B K 7 F 6 E 8 3 8 G 2 2 D H (a) Step through Dijkstra's algorithm to calculate the single-source shortest paths from vertex L to every other vertex by filling in the table as done in class. Cross out old values and write in new ones, from left to right, as the algorithm proceeds. (b) Write down the order in which Dijkstra's algorithm would mark each node as known. (e) Write down the shortest (weighted) path from L to B and its length (weighted cost). (d) Draw the minimum Spanning Tree of the graph