12. (10 Points) Consider the following directed, weighted graph, A 1 B 3 st 4 3...

   

Transcribed Image Text:

12. (10 Points) Consider the following directed, weighted graph, A 1 B 3 st 4 3 2 2 1 E 2 F 2 Step through Dijkstra's shortest path algorithm to calculate the single- source shortest paths from A to every other vertex. Show your steps in the table below. Cross out old values and write in new ones, from left to right within each cell, as the algorithm proceeds. Also list the lowest- cost path from vertex A to vertices including vertex F. 12a. (6 Points) Fill in the blanks. [ANSWER] Vertex Shortest Distance from A Previous Vertex A 0 B 1 A C 4 A D E F 12b. (4 Points) What is the shortest path from A to F in the graph, as computed above. [ANSWER] 12. (10 Points) Consider the following directed, weighted graph, A 1 B 3 st 4 3 2 2 1 E 2 F 2 Step through Dijkstra's shortest path algorithm to calculate the single- source shortest paths from A to every other vertex. Show your steps in the table below. Cross out old values and write in new ones, from left to right within each cell, as the algorithm proceeds. Also list the lowest- cost path from vertex A to vertices including vertex F. 12a. (6 Points) Fill in the blanks. [ANSWER] Vertex Shortest Distance from A Previous Vertex A 0 B 1 A C 4 A D E F 12b. (4 Points) What is the shortest path from A to F in the graph, as computed above. [ANSWER]