Question: 2. 1 -2 -3 2 1 (a) Even though the graph has negative weight edges, step through Dijkstra's algorithm to calculate supposedly shortest paths from

2. 1 -2 -3 2 1 (a) Even though the graph has negative weight edges, step through Dijkstra's algorithm to calculate supposedly shortest paths from A to every other vertex. Show your steps in a table. Cross out old values and write in new ones, from left to right within each cell, as the algorithm proceeds. Also list the vertices in the order which you marked them known. (b) Did Dijkstra's algorithm find the wrong path to some of the vertices? For just the vertices where the wrong path was computed, indicate both the path that was computed and the correct path. (c) Can a single edge be removed from the graph such that Dijkstra's algorithm would happen to compute correct answers for all vertices in the remaining graph? If so, which one
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
