Q$1$: $(30$ points$)-$ Dijkstra's Algorithm

You are provided with a directed weighted graph. Some of the edges have negative weights but solve through them to find the following:

a$)$ For the directed graph above, use the Dijkstra Algorithm to calculate the shortest path from A to every other node and the distance for that path.

b$)$ The Dijkstra Algorithm did not find the shortest path for all of the vertices. For the vertices which do not have the shortest path, write both the computed path with Dijkstra and the actual shortest path.

c$)$ Explain why in part b$,$ Dijkstra was not able to compute the shortest path. How will you modify the graph by making minimal changes so that Dijkstra is able to then find the shortest path. Q$2(20$ Points$)-$ Minimum Spanning Tree Algorithms

You can find an undirected weighted graph below. Answer the following questions:

a$)$ Apply the Prim's algorithm to calculate the minimum spanning tree from the vertex A$.$ Show the steps and all the values as you go through the algorithm. Also mention the distance for each of the paths. You can break the tie breaker of two paths with the same distance using the alphabetical order.

b$)$ Step through Kruskal's algorithm to calculate a minimum spanning tree of the graph. Show the disjoint sets at each iteration along with the edge cost and running cost. If you can select two edges with the same weight, select the edge that would come alphabetically last $($e$.$g$.,$ select $\backslash (\backslash$mathrm$\{$E$\}-\backslash$mathrm$\{$F$\}\backslash )$ before $\backslash (\backslash$mathrm$\{$B$\}-\backslash$mathrm$\{$C$\}\backslash ).$ Also, select $\backslash (\backslash$mathrm$\{$A$\}-\backslash$mathrm$\{$F$\}\backslash )$ before $\backslash (\backslash$mathrm$\{$A$\}-\backslash$mathrm$\{$B$\}\backslash )).$