Dijkstras: The following questions test your knowledge of Dijkstras algorithm. The various parts are not related to each other in this question. You can use drawing/handwriting for parts (b) and (c). (a) (10pt) Suppose Dijkstras algorithm runs on the following graph, starting at node A. A B C E F G 1 2 5 4 8 66 1 2 Fill in the following table with the intermediate distance values of all the nodes at each iteration of the algorithm. The first two columns are already filled in for you. Iteration Node 0 1 2 3 4 5 6 [add more columns if needed] A 0 0 B 1 C E 4 F 8 G (b) (10pt) Draw a graph with no negative cycles for which Dijkstras algorithm produces the wrong answer. Your graph must have no more than five vertices. Indicate the source where Dijkstras algorithm will be started from. (c) (10pt) Draw a graph with at least two negative weight edge for which Dijkstras algorithm produces the correct answer. Your graph must have no more than five vertices. Indicate the source where Dijkstras algorithm will be started from. Label each vertex with the distance produced by Dijkstras as well as with the correct distance. (d) (10pt) Professor Johnson suggests the following algorithm for finding the shortest path from node u to node w in a directed graph with some negative edges: add a large constant to each edge weight so that all the weights become positive, then run Dijkstras algorithm starting at node u, and return the shortest path found to node w. You realize though that this algorithm will not always work. Give an example of a weighted directed graph for which Professor Johnsons strategy wont work. Your example should not have more than 5 vertices. You can use handwriting for this part.

4. (40 pts.) Dijkstra's: The following questions test your knowledge of Dijkstra's algorithm. The various parts are not related to each other in this question. You can use drawing/handwriting for parts (b) and (c). (a) (10pt) Suppose Dijkstra's algorithm runs on the following graph, starting at node A. Fill in the following table with the intermediate distance values of all the nodes at each iteration of the algorithm. The first two columns are already filled in for you. (b) (10pt) Draw a graph with no negative cycles for which Dijkstra's algorithm produces the wrong answer. Your graph must have no more than five vertices. Indicate the source where Dijkstra's algorithm will be started from. (c) (10pt) Draw a graph with at least two negative weight edge for which Dijkstra's algorithm produces the correct answer. Your graph must have no more than five vertices. Indicate the source where Dijkstra's algorithm will be started from. Label each vertex with the distance produced by Dijkstra's as well as with the correct distance. (d) (10pt) Professor Johnson suggests the following algorithm for finding the shortest path from node u to node w in a directed graph with some negative edges: add a large constant to each edge weight so that all the weights become positive, then run Dijkstra's algorithm starting at node u, and return the shortest path found to node w. You realize though that this algorithm will not always work. Give an example of a weighted directed graph for which Professor Johnson's strategy won't work. Your example should not have more than 5 vertices. You can use handwriting for this part. 4. (40 pts.) Dijkstra's: The following questions test your knowledge of Dijkstra's algorithm. The various parts are not related to each other in this question. You can use drawing/handwriting for parts (b) and (c). (a) (10pt) Suppose Dijkstra's algorithm runs on the following graph, starting at node A. Fill in the following table with the intermediate distance values of all the nodes at each iteration of the algorithm. The first two columns are already filled in for you. (b) (10pt) Draw a graph with no negative cycles for which Dijkstra's algorithm produces the wrong answer. Your graph must have no more than five vertices. Indicate the source where Dijkstra's algorithm will be started from. (c) (10pt) Draw a graph with at least two negative weight edge for which Dijkstra's algorithm produces the correct answer. Your graph must have no more than five vertices. Indicate the source where Dijkstra's algorithm will be started from. Label each vertex with the distance produced by Dijkstra's as well as with the correct distance. (d) (10pt) Professor Johnson suggests the following algorithm for finding the shortest path from node u to node w in a directed graph with some negative edges: add a large constant to each edge weight so that all the weights become positive, then run Dijkstra's algorithm starting at node u, and return the shortest path found to node w. You realize though that this algorithm will not always work. Give an example of a weighted directed graph for which Professor Johnson's strategy won't work. Your example should not have more than 5 vertices. You can use handwriting for this part