Problem 3 This problem explores why Dijkstra's shortest-path algorithm only works when all edge weights are non-negative. Consider the following graph 4 -3 2 Now consider running Dijkstra's algorithm on the graph with A as the source node a. List the 4 vertices A, B, C, D in the order in which they would be extracted from the heap in our min-heap priority queue implementation of Dijkstra's algorithm, as well as the shortest-path value stored with each vertex at the time of its extraction First vertex Second vertex Third vertex: Fourth vertex: Shortest-path val Shortest-path val: Shortest-path val Shortest-path val c. Assume our implementation does not check whether the successor endpoint of a vertex has already been removed from the heap during a relaxation step, and that it performs the relaxation step for each vertex removed from the heap When vertex B is extracted from the heap, its outgoing edges will be considered for relaxation During the relaxation test of edge B -C, what numerical value will be tested as a candidate shortest-path value against vertex C's stored shortest-path value? d. In light of your answers to part (a), why is your answer to part (c) problematic? The existence of this problem is the reason Dijkstra's algorithm only works on graphs with non-negative-weight edges e. Suppose the weight of edge A-C is some real-valued variable x rather than 2. State the largest possible range of x-values that will cause Dijkstra's algorithm to return an incorrect answer (example answer format: 1 s x